Autumn 2000

1. Write a recursive function that returns the number of 1's in the binary representation of N for N>= 0. Use the fact that this is equal to the number of 1's in the representation of N/2, plus 1, if N is odd. Paper and pencil only. Trace it for N=7.

2. Page 35-36, Ex. 2.6 (Ex. 2.7 if you use the C++ book)

a. paper and pencil

b. requires coding simple loops and running them (see below)

c. compares results of a. and b.

3. Page 37, Ex. 2.9 (Ex. 2.13 if you use the C++ book), paper and pencil only. For part a, the "simple routine" to perform exponentiation is the one that uses i-1 multiplications to compute the ith power of X. For both parts a and b, each iteration is done by computing the ith power of X (brute force for a and efficiently for b), multiplying it by Ai and adding to the accumulated sum. Answer both parts in Big-Oh notation.

4. Page 37, Ex. 2.10 (Ex. 2.14 if you use the C++ book), a. and c. paper and pencil. Answer c. in Big-Oh notation. This is an alternative to the 2.9 approach.

How to time a segment of code:

#include <time.h>
void main()
{
   clock_t start, end, runTime;

   start = clock();

   /* Put your code here. */

   end = clock();
   runTime = end - start;
}