Scribd
Upload
31 views

Levitin

levitin

Uploaded by

nilanjanjanjan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views

Levitin

levitin

Uploaded by

nilanjanjanjan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

2.

3 Mathematical Analysis of Nonrecursive Algorithms 67

Exercises 2.3
1. Compute the following sums.
a. 1 + 3 + 5 + 7 + . . . + 999
b. 2 + 4 + 8 + 16 + . . . + 1024
n+1 n+1 n−1
c. i=3 1 d. i e. i(i + 1)
n +1
ni=3 n i=0
n
i=1 1/i(i + 1)
f. j
j =1 3 g. i=1 j =1 ij h.
2. Find the order of growth of the following sums. Use the (g(n)) notation with
the simplest function g(n) possible.
n−1 2 2 n−1 2
a. i=0 (i +1) b. i=2 lg i
n n−1 i−1
i=1(i + 1)2 j =0 (i + j )
c. i−1 d. i=0
3. The sample variance of n measurements x1, . . . , xn can be computed as either
n n
i=1(xi − x̄)
2 xi
where x̄ = i=1
n−1 n
or
n n
2
i=1 xi −( 2
i=1 xi ) /n
.
n−1
Find and compare the number of divisions, multiplications, and additions/
subtractions (additions and subtractions are usually bunched together) that
are required for computing the variance according to each of these formulas.
4. Consider the following algorithm.

ALGORITHM Mystery(n)
//Input: A nonnegative integer n
S←0
for i ← 1 to n do
S←S+i∗i
return S

a. What does this algorithm compute?


b. What is its basic operation?
c. How many times is the basic operation executed?
d. What is the efficiency class of this algorithm?
e. Suggest an improvement, or a better algorithm altogether, and indicate its
efficiency class. If you cannot do it, try to prove that, in fact, it cannot be
done.
76 Fundamentals of the Analysis of Algorithm Efficiency

A(2k ) = A(2k−1) + 1 for k > 0,


A(20) = 0.
Now backward substitutions encounter no problems:
A(2k ) = A(2k−1) + 1 substitute A(2k−1) = A(2k−2 ) + 1
= [A(2k−2 ) + 1] + 1 = A(2k−2 ) + 2 substitute A(2k−2 ) = A(2k−3) + 1
= [A(2k−3) + 1] + 2 = A(2k−3) + 3 ...
...
= A(2k−i ) + i
...
= A(2k−k ) + k.
Thus, we end up with
A(2k ) = A(1) + k = k,
or, after returning to the original variable n = 2k and hence k = log2 n,
A(n) = log2 n ∈ (log n).
In fact, one can prove (Problem 7 in this section’s exercises) that the exact solution
for an arbitrary value of n is given by just a slightly more refined formula A(n) =
log2 n.

This section provides an introduction to the analysis of recursive algorithms.


These techniques will be used throughout the book and expanded further as
necessary. In the next section, we discuss the Fibonacci numbers; their analysis
involves more difficult recurrence relations to be solved by a method different
from backward substitutions.

Exercises 2.4
1. Solve the following recurrence relations.
a. x(n) = x(n − 1) + 5 for n > 1, x(1) = 0
b. x(n) = 3x(n − 1) for n > 1, x(1) = 4
c. x(n) = x(n − 1) + n for n > 0, x(0) = 0
d. x(n) = x(n/2) + n for n > 1, x(1) = 1 (solve for n = 2k )
e. x(n) = x(n/3) + 1 for n > 1, x(1) = 1 (solve for n = 3k )
2. Set up and solve a recurrence relation for the number of calls made by F (n),
the recursive algorithm for computing n!.
3. Consider the following recursive algorithm for computing the sum of the first
n cubes: S(n) = 13 + 23 + . . . + n3.
2.4 Mathematical Analysis of Recursive Algorithms 77

ALGORITHM S(n)
//Input: A positive integer n
//Output: The sum of the first n cubes
if n = 1 return 1
else return S(n − 1) + n ∗ n ∗ n

a. Set up and solve a recurrence relation for the number of times the algo-
rithm’s basic operation is executed.
b. How does this algorithm compare with the straightforward nonrecursive
algorithm for computing this sum?
4. Consider the following recursive algorithm.

ALGORITHM Q(n)
//Input: A positive integer n
if n = 1 return 1
else return Q(n − 1) + 2 ∗ n − 1

a. Set up a recurrence relation for this function’s values and solve it to deter-
mine what this algorithm computes.
b. Set up a recurrence relation for the number of multiplications made by this
algorithm and solve it.
c. Set up a recurrence relation for the number of additions/subtractions made
by this algorithm and solve it.
5. Tower of Hanoi
a. In the original version of the Tower of Hanoi puzzle, as it was published in
the 1890s by Édouard Lucas, a French mathematician, the world will end
after 64 disks have been moved from a mystical Tower of Brahma. Estimate
the number of years it will take if monks could move one disk per minute.
(Assume that monks do not eat, sleep, or die.)
b. How many moves are made by the ith largest disk (1 ≤ i ≤ n) in this
algorithm?
c. Find a nonrecursive algorithm for the Tower of Hanoi puzzle and imple-
ment it in the language of your choice.
6. Restricted Tower of Hanoi Consider the version of the Tower of Hanoi
puzzle in which n disks have to be moved from peg A to peg C using peg
B so that any move should either place a disk on peg B or move a disk from
that peg. (Of course, the prohibition of placing a larger disk on top of a smaller
one remains in place, too.) Design a recursive algorithm for this problem and
find the number of moves made by it.

You might also like