Assignment I

Due date Feb.4.

1. From text: problems R-1.13, R-1.14 (page 48).

2. From text: C-1.3 (page 50).

3. From text : C-1.18 and C-1.19 (the wrong estimate for the Fibonnaci series, and the right one).

4. The function f (x) = log* (x) has an important role in the analysis of algorithms. It is defined as follows: log * (x) is the number of times we have to apply the log function (base 2, as usual) to x in order to get 1. For example, log* (16) = 3.

a) What is the number x for which log* (x) = 5?

b) Given the value of y = log* (x), can you write a closed-form expression for x as a function of y?

c) Astronomers usually give an estimate of 10 ^ 100 for the total number of elementary particles in the universe. What is the largest value of the log* function that we ever need to concern ourselves with?