The initial condition is verified immediately: (1) = 12=1
b. ()=(−1) + 1 for 1(1) = 0Solving it by backward
substitutions (it’s almost identical to the factorial example–see Example
1 in the section) or by applying the formula for the th term of an arith-
5. a. The number of moves is given by the formula: ()=2
−1Hence
b. Observe that for every move of the th disk, the algorithm first moves
the tower of all the disks smaller than it to another peg (this requires one
move of the (+1)st disk) and then, after the move of the th disk, this
Its solution is ()=2
−1for =12 (The easiest way to obtain
this formula is to use the formula for the generic term of a geometric
progression.) Note that the answer agrees nicely with the formula for the
total number of moves:
41
It can be solved by backward substitutions as follows
7. a. We’ll verify by substitution that ()=blog2csatisfies the recurrence
for the number of additions
()=(b2c)+1 for every 1
Let be even, i.e., =2
The left-hand side is:
()=blog2c=blog22c=blog22+log
2c=(1+blog2c)=
42
b. The recurrence relation for the number of additions is identical to
the one for the recursive version:
8. a. Algorithm Power()
−1+2
−1
b. ()=2(−1) + 1(0) = 0
c. The tree of recursive calls for this algorithm looks as follows:
n
Note that it has one extra level compared to the similar tree for the Tower
of Hanoi puzzle.
43
9. a. The algorithm computes the value of the smallest element in a given
array.
10. Let ()be the number of times the adjacency matrix element is checked
in the worst case (the graph is complete). We have the following recurrence
for ()
()=(−1) + −1for 1(1) = 0
11. a. Let ()be the number of multiplications made by the algorithm
based on the formula det =P−1
=0 0det If we don’t include
multiplications by , which are just ±1then
44
12. The number of squares added on the th iteration to each of the four
symmertic sides of the von Neumann neighborhood is equal to Hence
Solving the recurrence by backward substitutions yields the following:
()=(−1) + 4
13. a. Let ()be the number of minutes needed to fry hamburgers by the
algorithm given. Then we have the following recurrence for ():
()=(−2) + 2 for 2(1) = 2(2) = 2
c. If ≤2fry the hamburger (or the two hamburgers together if =2)
on each side. If =3fry the pancakes in 3 minutes as indicated in the
answer to the part b question. If 3fry two hamburgers together
on each side and then fry the remaining −2hamburgers by the same
algorithm. The recurrence for the number of minutes needed to fry
hamburgers looks now as follows:
45
14. The problem can be solved by a recursive algorithm. Indeed, by asking
just one question, we can eliminate the number of people who can be a
celebrity by 1, solve the problem for the remaining group of −1people
recursively, and then verify the returned solution by asking no more than
two questions. Here is a more detailed description of this algorithm:
If =1return that one person as a celebrity. If 1proceed as
follows:
Step 3 If the solution returned in Step 2 indicates that there is no celebrity
among the group of −1people, the larger group of people cannot
contain a celebrity either. If Step 2 identified as a celebrity a person
other than either A or B, say, C, ask whether C knows the person removed
Therecurrencefor(), the number of questions needed in the worst case,
is as follows:
()=(−1) + 3 for 2(2) = 2(1) = 0
46
Exercises 2.5
1. Find a Web site dedicated to applications of the Fibonacci numbers and
study it.
2. Fibonacci’s rabbits problem A man put a pair of rabbits in a place sur-
rounded by a wall. How many pairs of rabbits will be there in a year if the
4. How many even numbers are there among the first Fibonacci numbers?
Give a closed-form formula valid for every 0
5. Check by direct substitutions that the function 1
√5(−ˆ
)indeed satisfies
recurrence (2.6) and initial conditions (2.7).
6. The maximum values of the Java primitive types int and long are 231 −1
8. Improve algorithm ofthetextsothatitrequiresonlyΘ(1) space.
9. Prove the equality
12. In the language of your choice, implement two algorithms for computing
the last five digits of the th Fibonacci number that are based on (a)
Hints to Exercises 2.5
1. Use a search engine.
2. Set up an equation expressing the number of rabbits after months in
terms of the number of rabbits in some previous months.
6. Use an approximate formula for ()to find the smallest values of to
exceed the numbers given.
7. Set up the recurrence relations for ()and ()with appropriate initial
conditions, of course.
8. All the information needed on each iteration of the algorithm is the values
of the last two consecutive Fibonacci numbers. Modify the algorithm to
take advantage of this fact.
49
Solutions to Exercises 2.5
1. n/a
2. Let ()be the number of rabbit pairs at the end of month Clearly,
(0) = 1 and (1) = 1. For every 1, the number of rabbit pairs,
(), is equal to the number of pairs at the end of month −1,(−1),
Thefollowingtablegivesthevaluesofthefirst thirteen terms of the se-
quence, called the Fibonacci numbers,defined by this recurrence relation:
0 1 2 3 4 5 6 7 8 9 10 11 12
()11235813 21 34 55 89 144 233
3. Let ()be the number of different ways to climb an -stair staircase.
(−1) of them start with a one-stair climb and (−2) of them start
with a two-stair climb. Thus,
4. Starting with (0) = 0 and (1) = 1 and the rule ()=(−1) +
(−2) for every subsequent element of the sequence, it’s easy to see
50
5. On substituting into the left-hand side of the equation, we obtain
()−(−1) −(−2) = −−1−−2=−2(2−−1) = 0
because is one of the roots of the characteristic equation 2−−1=0
6. a. The question is to find the smallest value of such that ()231 −1
Using the formula ()= 1
√5rounded to the nearest integer, we get
(approximately) the following inequality:
ln(√5(263 −1))
ln ≈924
Thus, the answer is =93
7. Since ()is computed recursively by the formula ()=(−1) +
(−2)the recurrence equations for ()and ()will be the same as
8. Algorithm Fib2( )
//Computes the -th Fibonacci number using just two variables
//Input: A nonnegative integer
9. (i) The validity of the equality for =1follows immediately from the
definition of the Fibonacci sequence.
(ii) Assume that
52
10. The principal observation here is the fact that Euclid’s algorithm replaces
two consecutive Fibonacci numbers as its input by another pair of consec-
utive Fibonacci numbers, namely:
Therefore for every ≥4the quotient and remainder of division of ()
by (−1) are 1 and ()−(−1) = (−2)respectively. This
is exactly what we asserted at the beginning of the solution. In turn, this
leads to the following recurrence for the number of of divisions ():
11. Given a rectangle with sides ()and (+1)the problem can be
solved by the following recursive algorithm. If =1the problem is
already solved because the rectangle is a 1×1square. If 1dissect
the rectangle into the ()×()square and the rectangle with sides
(−1) and ()and then dissect the latter by the same algorithm. The
12. n/a
54
Exercises 2.6
1. Consider the following well-known sorting algorithm (we shall study it
more closely later in the book) with a counter inserted to count the num-
ber of key comparisons.
Is the comparison counter inserted in the right place? If you believe it is,
prove it; if you believe it is not, make an appropriate correction.
2. a. Run the program of Problem 1, with a properly inserted counter (or
counters) for the number of key comparisons, on 20 random arrays of sizes
1000, 1500, 2000, 2500,…,9000, 9500.
3. Repeat Problem 2 by measuring the program’s running time in millisec-
onds.
4. Hypothesize a likely efficiency class of an algorithm based on the following
empirical observations of its basic operation’s count:
7. a. Find empirically the largest number of divisions made by Euclid’s al-
gorithm for computing gcd( )for 1≤≤≤100
8. The average-case efficiency of Euclid’s algorithm on inputs of size can
be measured by the average number of divisions ()made by the
algorithm in computing gcd( 1)gcd( 2)…, gcd( )For example,
56
Hints to Exercises 2.6
1. Does it return a correct comparison count for every array of size 2?
2. Debug your comparison counting and random input generating for small
array sizes first.
6. Compare the values of the functions lg lg and lg for =2
7. Insert the division counter into a program implementing the algorithm
and run it for the input pairs in the range indicated.
Solutions to Exercises 2.6
1. It doesn’t count the comparison []when the comparison fails (and,
hence, the body of the while loop is not executed). If the language
implies that the second comparison will always be executed even if the
2. a. One should expect numbers very close to 24(the approximate the-
oretical number of key comparisons made by insertion sort on random
3. See the answers to Exercise 2. Note, however, that the timing data is
inherently much less accurate and volatile than the counting data.
6. The function lg lg grows much more slowly than the slow-growing func-
tion lg Also, if we transform the plots by substitution =2
the plot
of the former would look logarithmic while the plot of the latter would
appear linear.
7. a. 9 (for =89and = 55)
58
8. The experiment should confirm the known theoretical result: the average–
case efficiency of Euclid’s algorithm is in Θ(lg )For a slightly different
9. n/a