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?