# Solution Manual For Introduction To The Design And Analysis Of Algorithms, 3rd Edition

Preview Extract

This file contains the exercises, hints, and solutions for Chapter 2 of the
book โIntroduction to the Design and Analysis of Algorithms,โ 3rd edition, by
A. Levitin. The problems that might be challenging for at least some students
are marked by B; those that might be di๏ฌcult for a majority of students are
marked by I ๏บ
Exercises 2.1
1. For each of the following algorithms, indicate (i) a natural size metric for
its inputs, (ii) its basic operation, and (iii) whether the basic operation
count can be di๏ฌerent for inputs of the same size:
a. computing the sum of ๏ฎ numbers
b. computing ๏ฎ!
c. finding the largest element in a list of ๏ฎ numbers
d. Euclidโs algorithm
e. sieve of Eratosthenes
f. pen-and-pencil algorithm for multiplying two ๏ฎ-digit decimal integers
2. a. Consider the definition-based algorithm for adding two ๏ฎ ร ๏ฎ matrices.
What is its basic operation? How many times is it performed as a function
of the matrix order ๏ฎ? As a function of the total number of elements in
the input matrices?
b. Answer the same questions for the definition-based algorithm for matrix
multiplication.
3. Consider a variation of sequential search that scans a list to return the
number of occurrences of a given search key in the list. Will its e๏ฌciency
di๏ฌer from the e๏ฌciency of classic sequential search?
4. a. Glove selection There are 22 gloves in a drawer: 5 pairs of red gloves,
4 pairs of yellow, and 2 pairs of green. You select the gloves in the dark
and can check them only after a selection has been made. What is the
smallest number of gloves you need to select to have at least one matching
pair in the best case? in the worst case?
b. Missing socks Imagine that after washing 5 distinct pairs of socks,
you discover that two socks are missing. Of course, you would like to have
the largest number of complete pairs remaining. Thus, you are left with
4 complete pairs in the best-case scenario and with 3 complete pairs in
the worst case. Assuming that the probability of disappearance for each
1
of the 10 socks is the same, find the probability of the best-case scenario;
the probability of the worst-case scenario; the number of pairs you should
expect in the average case.
5. a.B Prove formula (2.1) for the number of bits in the binary representation
of a positive integer.
b.B Prove the alternative formula for the number of bits in the binary
representation of a positive integer ๏ฎ:
๏ข = dlog2 (๏ฎ + 1)e๏บ
c. What would be the analogous formulas for the number of decimal
digits?
d. Explain why, within the accepted analysis framework, it does not matter whether we use binary or decimal digits in measuring ๏ฎโs size.
6. Suggest how any sorting algorithm can be augmented in a way to make
the best-case count of its key comparisons equal to just ๏ฎ โ 1 (๏ฎ is a listโs
size, of course). Do you think it would be a worthwhile addition to any
sorting algorithm?
7. Gaussian elimination, the classic algorithm for solving systems of ๏ฎ linear
equations in ๏ฎ unknowns, requires about 13 ๏ฎ3 multiplications, which is the
algorithmโs basic operation.
a. How much longer should you expect Gaussian elimination to work
on a system of 1000 equations versus a system of 500 equations?
b. You are considering buying a computer that is 1000 times faster than
the one you currently have. By what factor will the faster computer increase the sizes of systems solvable in the same amount of time as on the
old computer?
8. For each of the following functions, indicate how much the functionโs value
will change if its argument is increased fourfold.
โ
a. log2 ๏ฎ
b. ๏ฎ
c. ๏ฎ
d. ๏ฎ2
e. ๏ฎ3
f. 2๏ฎ
9. Indicate whether the first function of each of the following pairs has a
smaller, same, or larger order of growth (to within a constant multiple)
than the second function.
2
a. ๏ฎ(๏ฎ + 1) and 2000๏ฎ2
b. 100๏ฎ2 and 0๏บ01๏ฎ3
c. log2 ๏ฎ and ln ๏ฎ
d. log22 ๏ฎ and log2 ๏ฎ2
e. 2๏ฎโ1 and 2๏ฎ
f. (๏ฎ โ 1)! and ๏ฎ!
10. Invention of chess a. According to a well-known legend, the game of
chess was invented many centuries ago in northwestern India by a certain
sage. When he took his invention to his king, the king liked the game so
much that he o๏ฌered the inventor any reward he wanted. The inventor
asked for some grain to be obtained as follows: just a single grain of wheat
was to be placed on the first square of the chess board, two on the second,
four on the third, eight on the fourth, and so on, until all 64 squares had
been filled. If it took just 1 second to count each grain, how long would
it take to count all the grain due to him?
b. How long would it take if instead of doubling the number of grains for
each square of the chessboard, the inventor asked for adding two grains?
3
Hints to Exercises 2.1
1. The questions are indeed as straightforward as they appear, though some
of them may have alternative answers. Also, keep in mind the caveat
about measuring an integerโs size.
2. a. The sum of two matrices is defined as the matrix whose elements are
the sums of the corresponding elements of the matrices given.
b. Matrix multiplication requires two operations: multiplication and addition. Which of the two would you consider basic and why?
3. Will the algorithmโs e๏ฌciency vary on di๏ฌerent inputs of the same size?
4. a. Gloves are not socks: they can be right-handed and left-handed.
b. You have only two qualitatively di๏ฌerent outcomes possible.
the number of ways to get each of the two.
Count
5. a. First, prove first that if a positive decimal integer ๏ฎ has ๏ข digits in its
binary representation, then
2๏ขโ1 โค ๏ฎ ๏ผ 2๏ข ๏บ
Then, take logarithms to base 2 of the terms in this inequality.
b. The proof is similar to the proof of formula (2.1).
c. The formula will be the same, with just one small adjustment to account for the di๏ฌerent radix.
d. How can we switch from one logarithm base to another?
6. Insert a verification of whether the problem is already solved.
7. A similar question was investigated in the section.
8. Use either the di๏ฌerence between or the ratio of ๏ฆ (4๏ฎ) and ๏ฆ (๏ฎ)๏ป whichever
is more convenient for getting a compact answer. If it is possible, try to
get an answer that does not depend on ๏ฎ๏บ
9. If necessary, simplify the functions in question to single out terms defining
their orders of growth to within a constant multiple. (We will discuss
formal methods for answering such questions in the next section; however,
these questions can be answered without knowledge of such methods.)
P๏ฎ
10. a. Use the formula ๏ฉ=0 2๏ฉ = 2๏ฎ+1 โ 1.
b. Use the formula for the sum of the first ๏ฎ odd numbers or the formula for the sum of arithmetic progression.
4
Solutions to Exercises 2.1
1. The answers are as follows.
a. (i) ๏ฎ; (ii) addition of two numbers; (iii) no
b. (i) the magnitude of ๏ฎ, i.e., the number of bits in its binary representation; (ii) multiplication of two integers; (iii) no
c. (i) ๏ฎ; (ii) comparison of two numbers;
list scanning algorithm)
(iii) no (for the standard
d. (i) either the magnitude of the larger of two input numbers, or the
magnitude of the smaller of two input numbers, or the sum of the magnitudes of two input numbers; (ii) modulo division; (iii) yes
e. (i) the magnitude of ๏ฎ, i.e., the number of bits in its binary representation; (ii) elimination of a number from the list of remaining candidates
to be prime; (iii) no
f. (i) ๏ฎ; (ii) multiplication of two digits; (iii) no
2. a. Addition of two numbers. Itโs performed ๏ฎ2 times (once for each of
๏ฎ2 elements in the matrix being computed). .Since the total number of
elements in two given matrices is ๏ = 2๏ฎ2 ๏ป the total number of additions
can also be expressed as ๏ฎ2 = ๏๏ฝ2๏บ
b. Since on most computers multiplication takes longer than addition,
multiplication is a better choice for being considered the basic operation
of the standard algorithm for matrix multiplication. Each of ๏ฎ2 elements
of the product of two ๏ฎ-by-๏ฎ matrices is computed as the scalar (dot)
product of two vectors of size ๏ฎ๏ป which requires ๏ฎ multiplications. The
total number of multiplications is ๏ฎ ยท ๏ฎ2 = ๏ฎ3 = (๏๏ฝ2)3๏ฝ2 .
3. This algorithm will always make ๏ฎ key comparisons on every input of size
๏ฎ๏ป whereas this number may vary between ๏ฎ and 1 for the classic version
of sequential search.
4. a. The best-case number is, obviously, two. The worst-case number is
twelve: one more than the number of gloves of one handedness.
b. There are just two possible outcomes here: the two missing socks
make a pair (the best case) and the two missing stocks do not make a
pair (the worst case). The total number of di๏ฌerent outcomes (the ways
5
ยก ยข
to choose the missing socks) is 10
2 = 45๏บ The number of best-case ones
5
is 5; hence its probability is 45
= 19 ๏บ The number of worst-case ones is
8
45 โ 5 = 40; hence its probability is 40
45 = 9 ๏บ On average, you should
1
8
28
1
expect 4 ยท 9 + 3 ยท 9 = 9 = 3 9 matching pairs.
5. a. The smallest positive integer that has ๏ข binary digits in its binary
๏ขโ1
expansion is 10๏บ๏บ๏บ0
|{z}๏ป which is 2 ; the largest positive integer that has ๏ข
๏ขโ1
๏ขโ1
๏ขโ2
binary digits in its binary expansion is 11๏บ๏บ๏บ1
|{z}๏ป which is 2 +2 +๏บ๏บ๏บ+1 =
๏ขโ1
2๏ข โ 1๏บ Thus,
2๏ขโ1 โค ๏ฎ ๏ผ 2๏ข ๏บ
Hence
log2 2๏ขโ1 โค log2 ๏ฎ ๏ผ log2 2๏ข
or
๏ข โ 1 โค log2 ๏ฎ ๏ผ ๏ข๏บ
These inequalities imply that ๏ข โ 1 is the largest integer not exceeding
log2 ๏ฎ๏บ In other words, using the definition of the floor function, we conclude that
๏ข โ 1 = blog2 ๏ฎc or ๏ข = blog2 ๏ฎc + 1๏บ
b. If ๏ฎ ๏พ 0 has ๏ข bits in its binary representation, then, as shown in
part a,
2๏ขโ1 โค ๏ฎ ๏ผ 2๏ข ๏บ
Hence
2๏ขโ1 ๏ผ ๏ฎ + 1 โค 2๏ข
and therefore
log2 2๏ขโ1 ๏ผ log2 (๏ฎ + 1) โค log2 2๏ข
or
๏ข โ 1 ๏ผ log2 (๏ฎ + 1) โค ๏ข๏บ
These inequalities imply that ๏ข is the smallest integer not smaller than
log2 (๏ฎ + 1)๏บ In other words, using the definition of the ceiling function,
we conclude that
๏ข = dlog2 (๏ฎ + 1)e๏บ
c. ๏ = blog10 ๏ฎc + 1 = dlog10 (๏ฎ + 1)e๏บ
d. ๏ข = blog2 ๏ฎc + 1 โ log2 ๏ฎ = log2 10 log10 ๏ฎ โ (log2 10)๏, where ๏ =
6
blog10 ๏ฎc + 1๏บ That is, the two size metrics are about equal to within a
constant multiple for large values of ๏ฎ๏บ
6. Before applying a sorting algorithm, compare the adjacent elements of
its input: if ๏ก๏ฉ โค ๏ก๏ฉ+1 for every ๏ฉ = 0๏ป ๏บ๏บ๏ป ๏ฎ โ 2๏ป stop. Generally, it
is not a worthwhile addition because it slows down the algorithm on all
but very special inputs. Note that some sorting algorithms (notably
bubble sort and insertion sort, which are discussed in Sections 3.1 and
4.1, respectively) intrinsically incorporate this test in the body of the
algorithm.
7. a. ๏๏(2๏ฎ)
(๏ฎ) โ
๏ฃ๏ 31 (2๏ฎ)3
= 8, where ๏ฃ๏ is the time of one multiplication๏บ
๏ฃ๏ 31 ๏ฎ3
b. We can estimate the running time for solving systems of order ๏ฎ on
the old computer and that of order ๏ on the new computer as ๏๏ฏ๏ฌ๏ค (๏ฎ) โ
๏ฃ๏ 31 ๏ฎ3 and ๏๏ฎ๏ฅ๏ท (๏ ) โ 10โ3 ๏ฃ๏ 13 ๏ 3 ๏ป respectively, where ๏ฃ๏ is the time of
one multiplication on the old computer. Replacing ๏๏ฏ๏ฌ๏ค (๏ฎ) and ๏๏ฎ๏ฅ๏ท (๏ )
by these estimates in the equation ๏๏ฏ๏ฌ๏ค (๏ฎ) = ๏๏ฎ๏ฅ๏ท (๏ ) yields ๏ฃ๏ 31 ๏ฎ3 โ
10โ3 ๏ฃ๏ 31 ๏ 3 or ๏
๏ฎ โ 10๏บ
8. a. log2 4๏ฎ โ log2 ๏ฎ = (log2 4 + log2 ๏ฎ) โ log2 ๏ฎ = 2๏บ
b.
โ
โ4๏ฎ = 2๏บ
๏ฎ
c. 4๏ฎ
๏ฎ = 4๏บ
2
2
d. (4๏ฎ)
๏ฎ2 = 4 ๏บ
3
3
e. (4๏ฎ)
๏ฎ3 = 4 ๏บ
4๏ฎ
f. 22๏ฎ = 23๏ฎ = (2๏ฎ )3 ๏บ
9. a. ๏ฎ(๏ฎ + 1) โ ๏ฎ2 has the same order of growth (quadratic) as 2000๏ฎ2 to
within a constant multiple.
b. 100๏ฎ2 (quadratic) has a lower order of growth than 0.01๏ฎ3 (cubic).
c. Since changing a logarithmโs base can be done by the formula
log๏ก ๏ฎ = log๏ก ๏ข log๏ข ๏ฎ๏ป
all logarithmic functions have the same order of growth to within a constant multiple.
7
d. log22 ๏ฎ = log2 ๏ฎ log2 ๏ฎ and log2 ๏ฎ2 = 2 log ๏ฎ๏บ Hence log22 ๏ฎ has a higher
order of growth than log2 ๏ฎ2 ๏บ
e. 2๏ฎโ1 = 12 2๏ฎ has the same order of growth as 2๏ฎ to within a constant multiple๏บ
f. (๏ฎ โ 1)! has a lower order of growth than ๏ฎ! = (๏ฎ โ 1)!๏ฎ๏บ
10. a. The total number of grains due to the inventor is
64
X
๏ฉ=1
2๏ฉโ1 =
63
X
๏ช=0
2๏ช = 264 โ 1 โ 1๏บ8 ยท 1019 ๏บ
(It is many times more than one can get by planting with grain the entire
surface of the planet Earth.) If it took just one second to count each grain,
the total amount of time needed to count all these grains comes to about
585 billion years, over 100 times more than the estimated age of our planet.
b. Here, the total amount of grains would have been equal to
1 + 3 + ๏บ๏บ๏บ + (2 ยท 64 โ 1) = 642 ๏บ
With the same speed of counting one grain per second, he would have
needed less than one hour and fourteen minutes to count his modest reward.
8
Exercises 2.2
1. Use the most appropriate notation among ๏๏ป ฮ๏ป and โฆ to indicate the
time e๏ฌciency class of sequential search (see Section 2.1)
a. in the worst case.
b. in the best case.
c. in the average case.
2. Use the informal definitions of ๏๏ป ฮ๏ป and โฆ to determine whether the following assertions are true or false.
a. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ๏(๏ฎ3 )
b. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ๏(๏ฎ2 )
c. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ฮ(๏ฎ3 )
d. ๏ฎ(๏ฎ + 1)๏ฝ2 โ โฆ(๏ฎ)
3. For each of the following functions, indicate the class ฮ(๏ง(๏ฎ)) the function
belongs to. (Use the simplest ๏ง(๏ฎ) possible in your answers.) Prove your
assertions.
โ
b. 10๏ฎ2 + 7๏ฎ + 3
a. (๏ฎ2 + 1)10
c. 2๏ฎ lg(๏ฎ + 2)2 + (๏ฎ + 2)2 lg ๏ฎ2
d. 2๏ฎ+1 + 3๏ฎโ1
e. blog2 ๏ฎc
4. a. Table 2.1 contains values of several functions that often arise in analysis
of algorithms. These values certainly suggest that the functions
log ๏ฎ๏ป
๏ฎ๏ป
๏ฎ log ๏ฎ๏ป
๏ฎ2 ๏ป
๏ฎ3 ๏ป
2๏ฎ ๏ป
are listed in increasing order of their order of growth.
prove this fact with mathematical certainty?
๏ฎ!
Do these values
b. Prove that the functions are indeed listed in increasing order of their
order of growth.
5. Order the following functions according to their order of growth (from the
lowest to the highest):
โ
(๏ฎ โ 2)!๏ป 5 lg(๏ฎ + 100)10 ๏ป 22๏ฎ ๏ป 0๏บ001๏ฎ4 + 3๏ฎ3 + 1๏ป ln2 ๏ฎ, 3 ๏ฎ๏ป 3๏ฎ ๏บ
6. a. Prove that every polynomial of degree ๏ซ๏ป ๏ฐ(๏ฎ) = ๏ก๏ซ ๏ฎ๏ซ + ๏ก๏ซโ1 ๏ฎ๏ซโ1 +
ยท ยท ยท + ๏ก0 with ๏ก๏ซ ๏พ 0๏ป belongs to ฮ(๏ฎ๏ซ )๏บ
b. Prove that exponential functions ๏ก๏ฎ have di๏ฌerent orders of growth
for di๏ฌerent values of base ๏ก ๏พ 0๏บ
9
7. Prove (by using the definitions of the notations involved) or disprove (by
giving a specific counterexample) the following assertions.
a. If ๏ด(๏ฎ) โ ๏(๏ง(๏ฎ))๏ป then ๏ง(๏ฎ) โ โฆ(๏ด(๏ฎ))๏บ
b. ฮ(๏ฎ๏ง(๏ฎ)) = ฮ(๏ง(๏ฎ))๏ป where ๏ฎ ๏พ 0๏บ
c. ฮ(๏ง(๏ฎ)) = ๏(๏ง(๏ฎ)) โฉ โฆ(๏ง(๏ฎ))๏บ
d.B For any two nonnegative functions ๏ด(๏ฎ) and ๏ง(๏ฎ) defined on the set of
nonnegative integers, either ๏ด(๏ฎ) โ ๏(๏ง(๏ฎ))๏ป or ๏ด(๏ฎ) โ โฆ(๏ง(๏ฎ))๏ป or both.
8. B Prove the sectionโs theorem for
a. โฆ notation.
b. ฮ notation.
9. We mentioned in this section that one can check whether all elements of an
array are distinct by a two-part algorithm based on the arrayโs presorting.
a. If the presorting is done by an algorithm with the time e๏ฌciency in
ฮ(๏ฎ log ๏ฎ)๏ป what will be the time e๏ฌciency class of the entire algorithm?
b. If the sorting algorithm used for presorting needs an extra array of
size ๏ฎ๏ป what will be the space e๏ฌciency class of the entire algorithm?
10. The range of a finite nonempty set of ๏ฎ real numbers ๏ is defined as the
di๏ฌerence between the largest and smallest elements of ๏๏บ For each representation of ๏ given below, describe in English an algorithm to compute
the range. Indicate the time e๏ฌciency classes of these algorithms using
the most appropriate notation (๏๏ป ฮ๏ป or โฆ)๏บ
a. An unsorted array
b. A sorted array
c. A sorted singly linked list
d. A binary search tree
11. Lighter or heavier? You have ๏ฎ ๏พ 2 identical-looking coins and a twopan balance scale with no weights. One of the coins is a fake, but you do
not know whether it is lighter or heavier than the genuine coins, which all
weigh the same. Design a ฮ(1) algorithm to determine whether the fake
coin is lighter or heavier than the others.
10
12. B Door in a wall You are facing a wall that stretches infinitely in both
directions. There is a door in the wall, but you know neither how far
away nor in which direction. You can see the door only when you are
right next to it. Design an algorithm that enables you to reach the door
by walking at most ๏(๏ฎ) steps where ๏ฎ is the (unknown to you) number
of steps between your initial position and the door. [Par95]
11
Hints to Exercises 2.2
1. Use the corresponding counts of the algorithmโs basic operation (see Section 2.1) and the definitions of ๏๏ป ฮ๏ป and โฆ๏บ
2. Establish the order of growth of ๏ฎ(๏ฎ + 1)๏ฝ2 first and then use the informal
definitions of ๏๏ป ฮ๏ป and โฆ. (Similar examples were given in the section.)
3. Simplify the functions given to single out the terms defining their orders
of growth.
4. a. Check carefully the pertinent definitions.
b. Compute the ratio limits of every pair of consecutive functions on
the list.
5. First simplify some of the functions. Then, use the list of functions
in Table 2.2 to โanchorโ each of the functions given. Prove their final
placement by computing appropriate limits.
6. a. You can prove this assertion either by computing an appropriate limit
or by applying mathematical induction.
b. Compute lim ๏ก๏ฎ1 ๏ฝ๏ก๏ฎ2 ๏บ
๏ฎโโ
7. Prove the correctness of (a), (b), and (c) by using the appropriate definitions; construct a counterexample for (d) (e.g., by constructing two
functions behaving di๏ฌerently for odd and even values of their arguments).
8. The proof of part (a) is similar to the one given for the theoremโs assertion
in Section 2.2. Of course, di๏ฌerent inequalities need to be used to bound
the sum from below.
9. Follow the analysis plan used in the text when the algorithm was mentioned for the first time.
10. You may use straightforward algorithms for all the four questions asked.
Use the ๏ notation for the time e๏ฌciency class of one of them, and the ฮ
notation for the three others.
11. The problem can be solved in two weighings.
12. You should walk intermittently left and right from your initial position
until the door is reached.
12
Solutions to Exercises 2.2
1. a. Since ๏๏ท๏ฏ๏ฒ๏ณ๏ด (๏ฎ) = ๏ฎ๏ป ๏๏ท๏ฏ๏ฒ๏ณ๏ด (๏ฎ) โ ฮ(๏ฎ)๏บ
b. Since ๏๏ข๏ฅ๏ณ๏ด (๏ฎ) = 1๏ป ๏๏ข๏ฅ๏ณ๏ด (1) โ ฮ(1)๏บ
c. Since ๏๏ก๏ถ๏ง (๏ฎ) = ๏ฐ(๏ฎ+1)
+ ๏ฎ(1 โ ๏ฐ) = (1 โ ๏ฐ2 )๏ฎ + ๏ฐ2 where 0 โค ๏ฐ โค 1๏ป
2
๏๏ก๏ถ๏ง (๏ฎ) โ ฮ(๏ฎ)๏บ
2. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ๏ฎ2 ๏ฝ2 is quadratic. Therefore
a. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ๏(๏ฎ3 ) is true.
b. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ๏(๏ฎ2 ) is true.
c. ๏ฎ(๏ฎ + 1)๏ฝ2 โ ฮ(๏ฎ3 ) is false.
d. ๏ฎ(๏ฎ + 1)๏ฝ2 โ โฆ(๏ฎ) is true.
3. a. Informally, (๏ฎ2 + 1)10 โ (๏ฎ2 )10 = ๏ฎ20 โ ฮ(๏ฎ20 ) Formally,
2
10
lim (๏ฎ ๏ฎ+1)
20
๏ฎโโ
2
10
= lim (๏ฎ(๏ฎ+1)
= lim
2 )10
2
๏ฎโโ
10
Hence (๏ฎ + 1)
๏ฎโโ
20
โ ฮ(๏ฎ )๏บ
ยณ 2
๏ฎ +1
๏ฎ2
ยด10
ยก
ยข10
== lim 1 + ๏ฎ12
= 1๏บ
๏ฎโโ
Note: An alternative proof can be based on the binomial formula and
the assertion of Exercise 6a.
โ
โ
โ
10๏ฎ2 + 7๏ฎ + 3 โ 10๏ฎ2 = 10๏ฎ โ ฮ(๏ฎ)๏บ Formally,
q
q
โ
โ
2
2
= lim 10 + ๏ฎ7 + ๏ฎ32 = 10๏บ
lim 10๏ฎ ๏ฎ+7๏ฎ+3 = lim 10๏ฎ ๏ฎ+7๏ฎ+3
2
b. Informally,
๏ฎโโ
๏ฎโโ
๏ฎโโ
โ
Hence 10๏ฎ2 + 7๏ฎ + 3 โ ฮ(๏ฎ)๏บ
c. 2๏ฎ lg(๏ฎ + 2)2 + (๏ฎ + 2)2 lg ๏ฎ2 = 2๏ฎ2 lg(๏ฎ + 2) + (๏ฎ + 2)2 (lg ๏ฎ โ 1) โ
ฮ(๏ฎ lg ๏ฎ) + ฮ(๏ฎ2 lg ๏ฎ) = ฮ(๏ฎ2 lg ๏ฎ)๏บ
d. 2๏ฎ+1 + 3๏ฎโ1 = 2๏ฎ 2 + 3๏ฎ 13 โ ฮ(2๏ฎ ) + ฮ(3๏ฎ ) = ฮ(3๏ฎ )๏บ
e. Informally, blog2 ๏ฎc โ log2 ๏ฎ โ ฮ(log ๏ฎ)๏บ Formally, by using the inequalities ๏ธ โ 1 ๏ผ b๏ธc โค ๏ธ (see Appendix A), we obtain an upper bound
blog2 ๏ฎc โค log2 ๏ฎ
and a lower bound
blog2 ๏ฎc ๏พ log2 ๏ฎ โ 1 โฅ log2 ๏ฎ โ
1
1
log2 ๏ฎ (for every ๏ฎ โฅ 4) = log2 ๏ฎ๏บ
2
2
Hence blog2 ๏ฎc โ ฮ(log2 ๏ฎ) = ฮ(log ๏ฎ)๏บ
13
4. a. The order of growth and the related notations ๏๏ป โฆ, and ฮ deal with
the asymptotic behavior of functions as ๏ฎ goes to infinity. Therefore no
specific values of functions within a finite range of ๏ฎโs values, suggestive
as they might be, can establish their orders of growth with mathematical
certainty.
1
0
log ๏ฅ
2 ๏ฎ)
b. lim log๏ฎ2 ๏ฎ = lim (log
= lim ๏ฎ 1 2 = log2 ๏ฅ lim ๏ฎ1 = 0๏บ
(๏ฎ)0
๏ฎโโ
๏ฎโโ
๏ฎโโ
๏ฎโโ
๏ฎ
lim
= lim log1 ๏ฎ = 0๏บ
2
๏ฎโโ ๏ฎ log2 ๏ฎ
๏ฎโโ
2๏ฎ
lim ๏ฎ log
= lim log๏ฎ2 ๏ฎ = (see the first limit of this exercise) = 0๏บ
๏ฎ2
๏ฎโโ
๏ฎโโ
2
lim ๏ฎ๏ฎ3 = lim ๏ฎ1 = 0๏บ
๏ฎโโ
๏ฎโโ
3
3 0
2
2 0
2
(๏ฎ )
(๏ฎ )
3๏ฎ
๏ฎ
3
3
lim 2๏ฎ๏ฎ = lim (2
๏ฎ )0 = lim 2๏ฎ ln 2 = ln 2 lim 2๏ฎ = ln 2 lim (2๏ฎ )0
๏ฎโโ
๏ฎโโ
๏ฎโโ
๏ฎโโ
(๏ฎ)0
๏ฎ
6
6
= ln32 lim 2๏ฎ2๏ฎ
=
lim
=
lim
2
2
๏ฎ
ln 2
ln 2 ๏ฎโโ 2
ln 2 ๏ฎโโ (2๏ฎ )0
๏ฎโโ
= ln62 2 lim 2๏ฎ 1ln 2 = ln63 2 lim 21๏ฎ = 0๏บ
๏ฎโโ
๏ฎโโ
๏ฎโโ
๏ฎ
lim 2 = (see Example 3 in the section) 0๏บ
๏ฎโโ ๏ฎ!
5. (๏ฎ โ 2)! โ ฮ((๏ฎ โ 2)!)๏ป 5 lg(๏ฎ + 100)10 = 50 lg(๏ฎ + 100) โ ฮ(log ๏ฎ)๏ป 2โ2๏ฎ =
(22 )๏ฎ โ ฮ(4๏ฎ )๏ป 0๏บ001๏ฎ4 + 3๏ฎ3 + 1 โ ฮ(๏ฎ4 )๏ป ln2 ๏ฎ โ ฮ(log2 ๏ฎ)๏ป 3 ๏ฎ โ
1
ฮ(๏ฎ 3 )๏ป 3๏ฎ โ ฮ(3๏ฎ )๏บ The list of these functions ordered in increasing
order of growth looks as follows:
โ
5 lg(๏ฎ + 100)10 ๏ป ln2 ๏ฎ๏ป 3 ๏ฎ๏ป 0๏บ001๏ฎ4 + 3๏ฎ3 + 1๏ป 3๏ฎ ๏ป 22๏ฎ ๏ป (๏ฎ โ 2)!
๏ซ
๏ซโ1
6. a. lim ๏ฐ(๏ฎ)
= lim ๏ก๏ซ ๏ฎ +๏ก๏ซโ1๏ฎ๏ฎ๏ซ
๏ฎ๏ซ
๏ฎโโ
+๏บ๏บ๏บ+๏ก0
๏ฎโโ
๏ก0
= lim (๏ก๏ซ + ๏ก๏ซโ1
๏ฎ + ๏บ๏บ๏บ + ๏ฎ๏ซ )
๏ฎโโ
= ๏ก๏ซ ๏พ 0๏บ
Hence ๏ฐ(๏ฎ) โ ฮ(๏ฎ๏ซ )๏บ
b.
๏ก๏ฎ
lim 1๏ฎ = lim
๏ฎโโ ๏ก
๏ฎโโ
2
ยต
๏ก1
๏ก2
ยถ๏ฎ
โง
โจ 0 if ๏ก1 ๏ผ ๏ก2
1 if ๏ก1 = ๏ก2
=
โฉ
โ if ๏ก1 ๏พ ๏ก2
โ ๏ก๏ฎ1 โ ๏ฏ(๏ก๏ฎ2 )
โ ๏ก๏ฎ1 โ ฮ(๏ก๏ฎ2 )
โ ๏ก๏ฎ2 โ ๏ฏ(๏ก๏ฎ1 )
7. a. The assertion should be correct because it states that if the order of
growth of ๏ด(๏ฎ) is smaller than or equal to the order of growth of ๏ง(๏ฎ)๏ป then
14
the order of growth of ๏ง(๏ฎ) is larger than or equal to the order of growth
of ๏ด(๏ฎ)๏บ The formal proof is immediate, too:
๏ด(๏ฎ) โค ๏ฃ๏ง(๏ฎ) for all ๏ฎ โฅ ๏ฎ0 ๏ป where ๏ฃ ๏พ 0๏ป
implies
1
( )๏ด(๏ฎ) โค ๏ง(๏ฎ) for all ๏ฎ โฅ ๏ฎ0 ๏บ
๏ฃ
b. The assertion that ฮ(๏ฎ๏ง(๏ฎ)) = ฮ(๏ง(๏ฎ)) should be true because ๏ฎ๏ง(๏ฎ)
and ๏ง(๏ฎ) di๏ฌer just by a positive constant multiple and, hence, by the
definition of ฮ๏ป must have the same order of growth. The formal proof
has to show that ฮ(๏ฎ๏ง(๏ฎ)) โ ฮ(๏ง(๏ฎ)) and ฮ(๏ง(๏ฎ)) โ ฮ(๏ฎ๏ง(๏ฎ))๏บ Let
๏ฆ (๏ฎ) โ ฮ(๏ฎ๏ง(๏ฎ)); weโll show that ๏ฆ (๏ฎ) โ ฮ(๏ง(๏ฎ))๏บ Indeed,
๏ฆ (๏ฎ) โค ๏ฃ๏ฎ๏ง(๏ฎ) for all ๏ฎ โฅ ๏ฎ0 (where ๏ฃ ๏พ 0)
can be rewritten as
๏ฆ (๏ฎ) โค ๏ฃ1 ๏ง(๏ฎ) for all ๏ฎ โฅ ๏ฎ0 (where ๏ฃ1 = ๏ฃ๏ฎ ๏พ 0),
i.e., ๏ฆ (๏ฎ) โ ฮ(๏ง(๏ฎ))๏บ
Let now ๏ฆ (๏ฎ) โ ฮ(๏ง(๏ฎ)); weโll show that ๏ฆ (๏ฎ) โ ฮ(๏ฎ๏ง(๏ฎ)) for ๏ฎ ๏พ 0๏บ
Indeed, if ๏ฆ (๏ฎ) โ ฮ(๏ง(๏ฎ))๏ป
๏ฆ (๏ฎ) โค ๏ฃ๏ง(๏ฎ) for all ๏ฎ โฅ ๏ฎ0 (where ๏ฃ ๏พ 0)
and therefore
๏ฆ (๏ฎ) โค
๏ฃ
๏ฃ
๏ก๏ง(๏ฎ) = ๏ฃ1 ๏ฎ๏ง(๏ฎ) for all ๏ฎ โฅ ๏ฎ0 (where ๏ฃ1 = ๏พ 0),
๏ฎ
๏ฎ
i.e., ๏ฆ (๏ฎ) โ ฮ(๏ฎ๏ง(๏ฎ))๏บ
c. The assertion is obviously correct (similar to the assertion that ๏ก = ๏ข
if and only if ๏ก โค ๏ข and ๏ก โฅ ๏ข). The formal proof should show that
ฮ(๏ง(๏ฎ)) โ ๏(๏ง(๏ฎ)) โฉ โฆ(๏ง(๏ฎ)) and that ๏(๏ง(๏ฎ)) โฉ โฆ(๏ง(๏ฎ)) โ ฮ(๏ง(๏ฎ))๏ป
which immediately follow from the definitions of ๏๏ป โฆ, and ฮ๏บ
d. The assertion is false. The following pair of functions can serve as
a counterexample
โง
โง 2
โจ ๏ฎ if ๏ฎ is even
โจ ๏ฎ if ๏ฎ is even
๏ด(๏ฎ) =
and ๏ง(๏ฎ) =
โฉ 2
โฉ
๏ฎ if ๏ฎ is odd
๏ฎ if ๏ฎ is odd
15
8. a. We need to prove that if ๏ด1 (๏ฎ) โ โฆ(๏ง1 (๏ฎ)) and ๏ด2 (๏ฎ) โ โฆ(๏ง2 (๏ฎ)), then
๏ด1 (๏ฎ) + ๏ด2 (๏ฎ) โ โฆ(max{๏ง1 (๏ฎ)๏ป ๏ง2 (๏ฎ)}).
Proof Since ๏ด1 (๏ฎ) โ โฆ(๏ง1 (๏ฎ))๏ป there exist some positive constant ๏ฃ1
and some nonnegative integer ๏ฎ1 such that
๏ด1 (๏ฎ) โฅ ๏ฃ1 ๏ง1 (๏ฎ) for all ๏ฎ โฅ ๏ฎ1 ๏บ
Since ๏ด2 (๏ฎ) โ โฆ(๏ง2 (๏ฎ))๏ป there exist some positive constant ๏ฃ2 and some
nonnegative integer ๏ฎ2 such that
๏ด2 (๏ฎ) โฅ ๏ฃ2 ๏ง2 (๏ฎ) for all ๏ฎ โฅ ๏ฎ2 ๏บ
Let us denote ๏ฃ = min{๏ฃ1 ๏ป ๏ฃ2 } and consider ๏ฎ โฅ max{๏ฎ1 ๏ป ๏ฎ2 } so that we
can use both inequalities. Adding the two inequalities above yields the
following:
๏ด1 (๏ฎ) + ๏ด2 (๏ฎ) โฅ ๏ฃ1 ๏ง1 (๏ฎ) + ๏ฃ2 ๏ง2 (๏ฎ)
โฅ ๏ฃ๏ง1 (๏ฎ) + ๏ฃ๏ง2 (๏ฎ) = ๏ฃ[๏ง1 (๏ฎ) + ๏ง2 (๏ฎ)]
โฅ ๏ฃ max{๏ง1 (๏ฎ)๏ป ๏ง2 (๏ฎ)}๏บ
Hence ๏ด1 (๏ฎ) + ๏ด2 (๏ฎ) โ โฆ(max{๏ง1 (๏ฎ)๏ป ๏ง2 (๏ฎ)}), with the constants ๏ฃ and
๏ฎ0 required by the ๏ definition being min{๏ฃ1 ๏ป ๏ฃ2 } and max{๏ฎ1 ๏ป ๏ฎ2 }๏ป respectively.
b. The proof follows immediately from the theorem proved in the text
(the ๏ part), the assertion proved in part (a) of this exercise (the โฆ part),
and the definition of ฮ (see Exercise 7c)๏บ
9. a. Since the running time of the sorting part of the algorithm will still
dominate the running time of the second, itโs the former that will determine the time e๏ฌciency of the entire algorithm. Formally, it follows from
equality
ฮ(๏ฎ log ๏ฎ) + ๏(๏ฎ) = ฮ(๏ฎ log ๏ฎ)๏ป
whose validity is easy to prove in the same manner as that of the sectionโs
theorem.
b. Since the second part of the algorithm will use no extra space, the
space e๏ฌciency class will be determined by that of the first (sorting) part.
Therefore, it will be ฮ(๏ฎ)๏บ
10. a. Scan the array to find the maximum and minimum values among its
elements and then compute the di๏ฌerence between them. The algorithmโs
time e๏ฌciency is ฮ(๏ฎ)๏บ Note: Although one can find both the maximum
and minimum values in an ๏ฎ-element array with about 1.5๏ฎ comparisons
16
(see the solutions to Problem 5 in Exercises in 2.3 and Problem 2 in Exercises 5.1), it doesnโt change the linear e๏ฌciency class, of course.
b. For a sorted array, we can simply compute the di๏ฌerence between
its first and last elements: ๏[๏ฎ โ 1] โ ๏[0]๏บ The time e๏ฌciency class is
obviously ฮ(1)๏บ
c. The smallest element is in the first node of the list and hence its
values can be obtained in constant time. The largest element is in the
last node reachable only by the traversal of the entire list, which requires
linear time. Computing the di๏ฌerence between the two values requires
constant time. Hence, the time e๏ฌciency class is ฮ(๏ฎ)๏บ
d. The smallest (largest) element in a binary search tree is in the leftmost (rightmost) node. To reach it, one needs to start with the root and
follow the chain of left-child (right-child) pointers until a node with the
null left-child (right-child) pointer is reached. Depending on the structure
of the tree, this chain of nodes can be between 1 and ๏ฎ nodes long. Hence,
the time of reaching its last node will be in ๏(๏ฎ)๏บ The running time of the
entire algorithm will also be linear: ๏(๏ฎ) + ๏(๏ฎ) + ฮ(1) = ๏(๏ฎ)๏บ
11. The puzzle can be solved in two weighings as follows. Start by taking
aside one coin if ๏ฎ is odd and two coins if ๏ฎ is even. After that divide the
remaining even number of coins into two equal-size groups and put them
on the opposite pans of the scale. If they weigh the same, all these coins
are genuine and the fake coin is among the coins set aside. So we can
weigh the set aside group of one or two coins against the same number of
genuine coins: if the former weighs less, the fake coin is lighter, otherwise,
it is heavier. If the first weighing does not result in a balance, take the
lighter group and, if the number of coins in it is odd, add to it one of the
coins initially set aside (which must be genuine). Divide all these coins
into two equal-size groups and weigh them. If they weigh the same, all
these coins are genuine and therefore the fake coin is heavier; otherwise,
they contain the fake, which is lighter.
Note: The puzzle provides a very rare example of a problem that can
be solved in the same number of basic operations (namely, two weighings)
irrespective of how large the problemโs instance (here, the number of coins)
is. Of course, had we considered putting one coin on the scale as the
algorithmโs basic operation, the algorithmโs e๏ฌciency would have been in
ฮ(๏ฎ) instead of ฮ(1)๏บ
12. The key idea here is to walk intermittently right and left going each time
exponentially farther from the initial position. A simple implementation
of this idea is to do the following until the door is reached: For ๏ฉ = 0๏ป 1๏ป ๏บ๏บ๏บ๏ป
make 2๏ฉ steps to the right, return to the initial position, make 2๏ฉ steps to
the left, and return to the initial position again. Let 2๏ซโ1 ๏ผ ๏ฎ โค 2๏ซ ๏บ The
17
number of steps this algorithm will need to find the door can be estimated
above as follows:
๏ซโ1
X
๏ฉ=0
4 ยท 2๏ฉ + 3 ยท 2๏ซ = 4(2๏ซ โ 1) + 3 ยท 2๏ซ ๏ผ 7 ยท 2๏ซ = 14 ยท 2๏ซโ1 ๏ผ 14๏ฎ๏บ
Hence the number of steps made by the algorithm is in ๏(๏ฎ)๏บ (Note:
It is not di๏ฌcult to improve the multiplicative constant with a better
algorithm.)
18
Exercises 2.3
1. Compute the following sums.
a. 1 + 3 + 5 + 7 + ยท ยท ยท + 999
b. 2 + 4 + 8 + 16 + ยท ยท ยท + 1024
c.
f.
P๏ฎ+1
๏ฉ=3 1
P๏ฎ
๏ช+1
๏ช=1 3
d.
g.
P๏ฎ+1
๏ฉ=3 ๏ฉ
P๏ฎ
๏ฉ=1
e.
P๏ฎ
๏ช=1 ๏ฉ๏ช
h.
P๏ฎโ1
๏ฉ=0 ๏ฉ(๏ฉ + 1)
P๏ฎโ1
๏ฉ=0 1๏ฝ๏ฉ(๏ฉ + 1)
2. Find the order of growth of the following sums.
P
P
2
2
2
a. ๏ฎโ1
b. ๏ฎโ1
๏ฉ=0 (๏ฉ +1)
๏ฉ=2 lg ๏ฉ
c.
P๏ฎ
๏ฉโ1
๏ฉ=1 (๏ฉ + 1)2
d.
P๏ฎโ1 P๏ฉโ1
๏ฉ=0
๏ช=0 (๏ฉ + ๏ช)
Use the ฮ(๏ง(๏ฎ)) notation with the simplest function ๏ง(๏ฎ) possible.
3. The sample variance of ๏ฎ measurements ๏ธ1 ๏ป ๏ธ2 ๏ป ๏บ๏บ๏บ๏ป ๏ธ๏ฎ can be computed as
P๏ฎ
P๏ฎ
2
๏ธ๏ฉ
๏ฉ=1 (๏ธ๏ฉ โ ๏ธฬ)
where ๏ธฬ = ๏ฉ=1
๏ฎโ1
๏ฎ
or
P๏ฎ
P๏ฎ
2
2
๏ฉ=1 ๏ธ๏ฉ โ ( ๏ฉ=1 ๏ธ๏ฉ ) ๏ฝ๏ฎ
๏บ
๏ฎโ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( ๏ฎ)
//Input: A nonnegative integer ๏ฎ
๏โ0
for ๏ฉ โ 1 to ๏ฎ do
๏ โ๏+๏ฉโ๏ฉ
return ๏
a. What does this algorithm compute?
b. What is its basic operation?
c. How many times is the basic operation executed?
19
d. What is the e๏ฌciency class of this algorithm?
e. Suggest an improvement, or a better algorithm altogether, and indicate its e๏ฌciency class. If you cannot do it, try to prove that, in fact,
it cannot be done.
5. Consider the following algorithm.
Algorithm Secret(๏[0๏บ๏บ๏ฎ โ 1])
//Input: An array ๏[0๏บ๏บ๏ฎ โ 1] of ๏ฎ real numbers
minval โ ๏[0]; maxval โ ๏[0]
for ๏ฉ โ 1 to ๏ฎ โ 1 do
if ๏[๏ฉ] ๏ผ minval
minval โ ๏[๏ฉ]
if ๏[๏ฉ] ๏พ maxval
maxval โ ๏[๏ฉ]
return maxval โ minval
Answer questions aโe of Problem 4 about this algorithm.
6. Consider the following algorithm.
Algorithm Enigma(๏[0๏บ๏บ๏ฎ โ 1๏ป 0๏บ๏บ๏ฎ โ 1])
//Input: A matrix ๏[0๏บ๏บ๏ฎ โ 1๏ป 0๏บ๏บ๏ฎ โ 1] of real numbers
for ๏ฉ โ 0 to ๏ฎ โ 2 do
for ๏ช โ ๏ฉ + 1 to ๏ฎ โ 1 do
if ๏[๏ฉ๏ป ๏ช] 6= ๏[๏ช๏ป ๏ฉ]
return false
return true
Answer the questions aโe of Problem 4 about this algorithm.
7. Improve the implementation of the matrix multiplication algorithm (see
Example 3) by reducing the number of additions made by the algorithm.
What e๏ฌect will this change have on the algorithmโs e๏ฌciency?
8. Determine the asymptotic order of growth for the total number of times all
the doors are toggled in the locker doors puzzle (Problem 12 in Exercises
1.1).
9. Prove the formula
๏ฎ
X
๏ฉ=1
๏ฉ = 1 + 2 + ยทยทยท + ๏ฎ =
๏ฎ(๏ฎ + 1)
2
either by mathematical induction or by following the insight of a 10-yearold schoolboy named Karl Friedrich Gauss (1777โ1855) who grew up to
become one of the greatest mathematicians of all times.
20
10. Mental arithmetic A 10ร10 table is filled with repeating numbers on its
diagonals as shown below. Calculate the total sum of the tableโs numbers
in your head. (after [Cra07, Question 1.33])
1 2 3
2 3
9 10
9 10 11
3
9 10 11
9 10 11
9 10 11
9 10 11
9 10 11
9 10 11
9 10 11
10 11
17
17 18
17 18 19
11. Consider the following version of an important algorithm that we will
study later in the book.
Algorithm GE (๏[0..๏ฎ โ 1๏ป 0๏บ๏บ๏ฎ])
//Input: An ๏ฎ ร (๏ฎ + 1) matrix ๏[0๏บ๏บ๏ฎ โ 1๏ป 0๏บ๏บ๏ฎ] of real numbers
for ๏ฉ โ 0 to ๏ฎ โ 2 do
for ๏ช โ ๏ฉ + 1 to ๏ฎ โ 1 do
for ๏ซ โ ๏ฉ to ๏ฎ do
๏[๏ช๏ป ๏ซ] โ ๏[๏ช๏ป ๏ซ] โ ๏[๏ฉ๏ป ๏ซ] โ ๏[๏ช๏ป ๏ฉ] ๏ฝ ๏[๏ฉ๏ป ๏ฉ]
return ๏
a.B Find the time e๏ฌciency class of this algorithm.
b.B What glaring ine๏ฌciency does this pseudocode contain and how can
it be eliminated to speed the algorithm up?
12. von Neumannโs neighborhood How many one-by-one squares are generated by the algorithm that starts with a single square square and on each
of its ๏ฎ iterations adds new squares all round the outside. How many
one-by-one squares are generated on the ๏ฎth iteration? [Gar99] (In the
parlance of cellular automata theory, the answer is the number of cells in
the von Neumann neighborhood of range ๏ฎ.) The results for ๏ฎ = 0, 1, and
21
2 are illustrated below.
๏ฎ=0
๏ฎ=1
๏ฎ=2
13. Page numbering Find the total number of decimal digits needed for numbering pages in a book of 1000 pages. Assume that the pages are numbered consecutively starting with 1.
22
Hints to Exercises 2.3
1. Use the common summation formulas and rules listed in Appendix A. You
may need to perform some simple algebraic operations before applying
them.
2. Find a sum among those in Appendix A that looks similar to the sum in
question and try to transform the latter to the former. Note that you
do not have to get a closed-end formula for a sum before establishing its
order of growth.
3. Just follow the formulas in question.
4. a. Tracing the algorithm to get its output for a few small values of ๏ฎ (e.g.,
๏ฎ = 1๏ป 2๏ป and 3) should help if you need it.
b. We faced the same question for the examples discussed in the text.
One of them is particularly pertinent here.
c. Follow the plan outlined in the section.
d. As a function of ๏ฎ, the answer should follow immediately from your
answer to part (c). You may also want to give an answer as a function of
the number of bits in the ๏ฎโs representation (why?).
e. Have you not encountered this sum somewhere?
5. a. Tracing the algorithm to get its output for a few small values of ๏ฎ (e.g.,
๏ฎ = 1๏ป 2๏ป and 3) should help if you need it.
b. We faced the same question for the examples discussed in the section. One of them is particularly pertinent here.
c. You can either follow the sectionโs plan by setting up and computing a sum or answer the question directly. (Try to do both.)
d. Your answer will immediately follow from the answer to part (c).
e. Does the algorithm always have to make two comparisons on each
iteration? This idea can be developed further to get a more significant
improvement than the obvious oneโtry to do it for a four-element array
and then generalize the insight. But can we hope to find an algorithm
with a better than linear e๏ฌciency?
6. a. Elements ๏[๏ฉ๏ป ๏ช] and ๏[๏ช๏ป ๏ฉ] are symmetric with respect to the main
diagonal of the matrix.
b. There is just one candidate here.
23
c. You may investigate the worst case only.
d. Your answer will immediately follow from the answer to part (c).
e. Compare the problem the algorithm solves with the way it does this.
7. Computing a sum of ๏ฎ numbers can be done with ๏ฎ โ 1 additions. How
many does the algorithm make in computing each element of the product
matrix?
8. Set up a sum for the number of times all the doors and toggled and find
its asymptotic order of growth by using some properties from Appendix
A.
9. For the general step of the proof by induction, use the formula
๏ฎ
X
๏ฉ=
๏ฉ=1
๏ฎโ1
X
๏ฉ + ๏ฎ๏บ
๏ฉ=1
The young Gauss computed the sum 1 + 2 + ยท ยท ยท + 99 + 100 by noticing
that it can be computed as the sum of 50 pairs, each with the same sum.
10. There are at least two di๏ฌerent ways to solve this problem, which comes
from a collection of Wall Street interview questions.
11. a. Setting up a sum should pose no di๏ฌculties. Using the standard summation formulas and rules will require more e๏ฌort than in the previous
examples, however.
b. Optimize the algorithmโs innermost loop.
12. Set up a sum for the number of squares after ๏ฎ iterations of the algorithm
and then simplify it to get a closed-form answer.
13. To derive a formula expressing the total number of digits as a function of
the number of pages ๏ฎ๏ป where 1 โค ๏ฎ โค 1000๏ป itโs convenient to partition
the functionโs domain into several natural intervals.
24
Solutions to Exercises 2.3
1. a. 1+3+5+7+๏บ๏บ๏บ+999 =
500
P
(2๏ฉ-1) =
๏ฉ=1
500
P
2๏ฉ-
๏ฉ=1
500
P
๏ฉ=1
1 = 2 500โ501
-500 = 250๏ป 000๏บ
2
(Or by using the formula for the sum of odd integers:
500
P
(2๏ฉ-1) = 5002 =
๏ฉ=1
250๏ป 000๏บ
Or by using the formula for the sum of the arithmetic progression with
๏ฎ )๏ฎ
= (1+999)500
= 250๏ป 000๏บ)
๏ก1 = 1๏ป ๏ก๏ฎ = 999๏ป and ๏ฎ = 500: (๏ก1 +๏ก
2
2
b. 2 + 4 + 8 + 16 + ๏บ๏บ๏บ + 1๏ป 024 =
10
P
2๏ฉ =
๏ฉ=1
10
P
๏ฉ=0
2๏ฉ โ 1 = (211 โ 1) โ 1 = 2๏ป 046๏บ
(Or by using the formula for the sum of the geometric series with ๏ก = 2๏ป
๏ฎ+1
10
โ1
= 2๏ป 046๏บ)
๏ฑ = 2, and ๏ฎ = 9: ๏ก ๏ฑ ๏ฑโ1โ1 = 2 22โ1
c.
d.
e.
๏ฎ+1
P
๏ฉ=3
๏ฎ+1
P
๏ฉ=3
๏ฎโ1
P
1 = (๏ฎ + 1) โ 3 + 1 = ๏ฎ โ 1๏บ
๏ฉ=
๏ฎ+1
P
๏ฉ=0
๏ฉ(๏ฉ + 1) =
๏ฉ=0
g.
๏ฎ
P
3๏ช+1 = 3
๏ช=1
๏ฎ
๏ฎ P
P
๏ฉ๏ช =
๏ฉ=1 ๏ช=1
(๏ฉ2 + ๏ฉ) =
2
๏ฎ
P
3๏ช = 3[
๏ช=1
๏ฎ
P
๏ฉ
2
๏ฎโ1
P
๏ฉ2 +
๏ฉ=0
๏ฎ
P
P๏ฎ
๏ฎ
P
๏ฎโ1
P
๏ฉ=0
๏ฉ = (๏ฎโ1)๏ฎ(2๏ฎโ1)
+ (๏ฎโ1)๏ฎ
6
2
๏ฎ+1
๏ฎ+2
3๏ช โ 1] = 3[ 3 3โ1โ1 โ 1] = 3
๏ช=0
๏ฎ
P
๏ช=
๏ฉ=1 ๏ช=1
= ๏ฎ (๏ฎ+1)
๏บ
4
h.
๏ฉ=0
๏ฎโ1
P
2
๏ฉ = (๏ฎ+1)(๏ฎ+2)
โ 3 = ๏ฎ +3๏ฎโ4
๏บ
2
2
๏ฉ=0
2
= (๏ฎ โ1)๏ฎ
๏บ
3
f.
2
P
๏ฉโ
๏ฉ=1
๏ฉ ๏ฎ(๏ฎ+1)
= ๏ฎ(๏ฎ+1)
2
2
๏ฎ
P
๏ฉ=1
2
โ9
๏บ
๏ฎ(๏ฎ+1)
๏ฉ = ๏ฎ(๏ฎ+1)
2
2
P๏ฎ
1
1
๏ฉ=1 ( ๏ฉ โ ๏ฉ+1 )
๏ฉ=1 1๏ฝ๏ฉ(๏ฉ + 1) =
1
1
1
๏ฎ
โ ๏ฎ1 ) + ( ๏ฎ1 โ ๏ฎ+1
) = 1 โ ๏ฎ+1
= ๏ฎ+1
๏บ
= ( 11 โ 12 ) + ( 12 โ 13 ) + ๏บ๏บ๏บ + ( ๏ฎโ1
(This
is
a
special
case
of
the
so-called
telescoping
seriesโsee
Appendix
P
Aโ ๏ต๏ฉ=๏ฌ (๏ก๏ฉ โ ๏ก๏ฉโ1 ) = ๏ก๏ต โ ๏ก๏ฌโ1 .)
2. a.
๏ฎโ1
P
(๏ฉ2 + 1)2 =
๏ฉ=0
๏ฎโ1
P
(๏ฉ4 + 2๏ฉ2 + 1) =
๏ฉ=0
๏ฎโ1
P
๏ฉ4 + 2
๏ฉ=0
โ ฮ(๏ฎ5 ) + ฮ(๏ฎ3 ) + ฮ(๏ฎ) = ฮ(๏ฎ5 ) (or just
b.
๏ฎโ1
P
๏ฉ=2
log2 ๏ฉ2 =
๏ฎโ1
P
๏ฉ=2
2 log2 ๏ฉ = 2
๏ฎโ1
P
๏ฉ=2
25
๏ฉ=0
๏ฎโ1
P
๏ฉ=0
log2 ๏ฉ = 2
โ 2ฮ(๏ฎ log ๏ฎ) โ ฮ(log ๏ฎ) = ฮ(๏ฎ log ๏ฎ)๏บ
๏ฎโ1
P
๏ฉ2 +
๏ฎโ1
P
(๏ฉ2 + 1)2 โ
๏ฎ
P
๏ฉ=1
1
๏ฉ=0
๏ฎโ1
P
๏ฉ=0
๏ฉ4 โ ฮ(๏ฎ5 ))๏บ
log2 ๏ฉ โ 2 log2 ๏ฎ
c.
๏ฎ
P
(๏ฉ + 1)2๏ฉโ1 =
๏ฉ=1
๏ฎ
P
๏ฉ2๏ฉโ1 +
๏ฉ=1
๏ฎ
P
๏ฉ=1
โ ฮ(๏ฎ2๏ฎ ) + ฮ(2๏ฎ ) = ฮ(๏ฎ2๏ฎ ) (or
d.
๏ฎโ1
P ๏ฉโ1
P
(๏ฉ + ๏ช) =
๏ฎโ1
P ๏ฉโ1
P
[
๏ฉ+
2๏ฉโ1 = 12
๏ฎ
P
๏ฎ
P
๏ฉ2๏ฉ +
๏ฉ=1
(๏ฉ + 1)2๏ฉโ1 โ 12
๏ฉ=1
๏ฉโ1
P
๏ช] =
๏ฎโ1
P
๏ฎโ1
P
๏ช=0
๏ฎ
P
๏ฉ=1
2๏ช
๏ฉ2๏ฉ โ ฮ(๏ฎ2๏ฎ ))๏บ
[๏ฉ2 + (๏ฉโ1)๏ฉ)
]=
2
๏ฉ=0 ๏ช=0
๏ฉ=0 ๏ช=0
๏ช=0
๏ฉ=0
๏ฎโ1
๏ฎโ1
P
P
๏ฉ2 โ 12
๏ฉ โ ฮ(๏ฎ3 ) โ ฮ(๏ฎ2 ) = ฮ(๏ฎ3 )๏บ
= 32
๏ฉ=0
๏ฉ=0
๏ฎโ1
P
๏ฉ=0
[ 32 ๏ฉ2 โ 12 ๏ฉ]
3. For the first formula: ๏(๏ฎ) = 2๏ป ๏ (๏ฎ) = ๏ฎ๏ป ๏(๏ฎ) + ๏(๏ฎ) = [(๏ฎ โ 1) +
(๏ฎ โ 1)] + (๏ฎ + 1) = 3๏ฎ โ 1๏บ
For the second formula: ๏(๏ฎ) = 2๏ป ๏ (๏ฎ) = ๏ฎ + 1๏ป
[(๏ฎ โ 1) + (๏ฎ โ 1)] + 2 = 2๏ฎ๏บ
4. a. Computes ๏(๏ฎ) =
๏(๏ฎ) + ๏(๏ฎ) =
๏ฎ
P
๏ฉ2 ๏บ
๏ฉ=1
b. Multiplication (or, if multiplication and addition are assumed to take
the same amount of time, either of the two).
c. ๏(๏ฎ) =
๏ฎ
P
1 = ๏ฎ.
๏ฉ=1
d. ๏(๏ฎ) = ๏ฎ โ ฮ(๏ฎ)๏บ Since the number of bits ๏ข = blog2 ๏ฎc + 1 โ log2 ๏ฎ
and hence ๏ฎ โ 2๏ข ๏ป ๏(๏ฎ) โ 2๏ข โ ฮ(2๏ข )๏บ
e. Use the formula
๏ฎ
P
๏ฉ2 = ๏ฎ(๏ฎ+1)(2๏ฎ+1)
to compute the sum in ฮ(1)
6
๏ฉ=1
time (which assumes that the time of arithmetic operations stay constant
irrespective of the size of the operationsโ operands).
5. a. Computes the range, i.e., the di๏ฌerence between the arrayโs largest and
smallest elements.
b. An element comparison.
c. ๏(๏ฎ) =
๏ฎโ1
P
๏ฉ=1
d. ฮ(๏ฎ)๏บ
2 = 2(๏ฎ โ 1).
e. An obvious improvement for some inputs (but not for the worst case)
is to replace the two if-statements by the following one:
if ๏[๏ฉ] ๏ผ minval minval โ ๏[๏ฉ]
26
else if ๏[๏ฉ] ๏พ maxval maxval โ ๏[๏ฉ]๏บ
Another improvement, both more subtle and substantial, is based on the
observation that it is more e๏ฌcient to update the minimum and maximum
values seen so far not for each element but for a pair of two consecutive
elements. If two such elements are compared with each other first, the
updates will require only two more comparisons for the total of three comparisons per pair. Note that the same improvement can be obtained by
a divide-and-conquer algorithm (see Problem 2 in Exercises 5.1).
6. a. The algorithm returns โtrueโ if its input matrix is symmetric and
โfalseโ if it is not.
b. Comparison of two matrix elements.
c. ๏๏ท๏ฏ๏ฒ๏ณ๏ด (๏ฎ) =
๏ฎโ2
P ๏ฎโ1
P
1=
๏ฉ=0 ๏ช=๏ฉ+1
=
๏ฎโ2
P
๏ฉ=0
๏ฎโ2
P
๏ฉ=0
[(๏ฎ โ 1) โ (๏ฉ + 1) + 1)
(๏ฎ โ 1 โ ๏ฉ) = (๏ฎ โ 1) + (๏ฎ โ 2) + ๏บ๏บ๏บ + 1 = (๏ฎโ1)๏ฎ
๏บ
2
d. Quadratic: ๏๏ท๏ฏ๏ฒ๏ณ๏ด (๏ฎ) โ ฮ(๏ฎ2 ) (or ๏(๏ฎ) โ ๏(๏ฎ2 ))๏บ
e. The algorithm is optimal because any algorithm that solves this problem must, in the worst case, compare (๏ฎ โ 1)๏ฎ๏ฝ2 elements in the uppertriangular part of the matrix with their symmetric counterparts in the
lower-triangular part, which is all this algorithm does.
7. Replace the body of the ๏ช loop by the following fragment:
๏[๏ฉ๏ป ๏ช] โ ๏[๏ฉ๏ป 0] โ ๏[0๏ป ๏ช]
for ๏ซ โ 1 to ๏ฎ โ 1 do
๏[๏ฉ๏ป ๏ช] โ ๏[๏ฉ๏ป ๏ช] + ๏[๏ฉ๏ป ๏ซ] โ ๏[๏ซ๏ป ๏ช]
This will decrease the number of additions from ๏ฎ3 to ๏ฎ3 โ ๏ฎ2 , but the
number of multiplications will still be ๏ฎ3 ๏บ The algorithmโs e๏ฌciency class
will remain cubic.
8. Let ๏ (๏ฎ) be the total number of times all the doors are toggled.
problem statement implies that
๏ (๏ฎ) =
The
๏ฎ
X
b๏ฎ๏ฝ๏ฉc๏บ
๏ฉ=1
Since ๏ธ โ 1 ๏ผ b๏ธc โค ๏ธ and
P๏ฎ
๏ฉ=1 1๏ฝ๏ฉ โ ln ๏ฎ + ๏ฐ, where ๏ฐ = 0๏บ5772๏บ๏บ๏บ( see
27
Appendix A),
๏ (๏ฎ) โค
๏ฎ
X
๏ฎ๏ฝ๏ฉ = ๏ฎ
๏ฉ=1
๏ฎ
X
๏ฉ=1
1๏ฝ๏ฉ โ ๏ฎ(ln ๏ฎ + ๏ฐ) โ ฮ(๏ฎ log ๏ฎ)๏บ
Similarly,
๏ (๏ฎ) ๏พ
๏ฎ
๏ฎ
๏ฎ
X
X
X
(๏ฎ๏ฝ๏ฉ โ 1) = ๏ฎ
1๏ฝ๏ฉ โ
1 โ ๏ฎ(ln ๏ฎ + ๏ฐ) โ ๏ฎ โ ฮ(๏ฎ log ๏ฎ)๏บ
๏ฉ=1
๏ฉ=1
๏ฉ=1
This implies that ๏ (๏ฎ) โ ฮ(๏ฎ log ๏ฎ)๏บ
Note: Alternatively, we could use the formula for approximating sums
by definite integrals (see Appendix A):
๏ (๏ฎ) โค
Z ๏ฎ
๏ฎ
X
1
๏ฎ๏ฝ๏ฉ = ๏ฎ(1+
1๏ฝ๏ฉ) โค ๏ฎ(1+
๏ค๏ธ) = ๏ฎ(1+ln ๏ฎ) โ ฮ(๏ฎ log ๏ฎ)
1 ๏ธ
๏ฉ=1
๏ฉ=2
๏ฎ
X
and
๏ (๏ฎ) ๏พ
Z ๏ฎ+1
๏ฎ
๏ฎ
๏ฎ
X
X
X
1
(๏ฎ๏ฝ๏ฉโ1) = ๏ฎ
1๏ฝ๏ฉโ
1โฅ๏ฎ
๏ค๏ธโ๏ฎ = ๏ฎ ln(๏ฎ+1)โ๏ฎ โ ฮ(๏ฎ log ๏ฎ)๏บ
๏ธ
1
๏ฉ=1
๏ฉ=1
๏ฉ=1
9. Here is a proof by mathematical induction that
๏ฎ
P
๏ฉ=1
positive integer ๏ฎ๏บ
(i) Basis step: For ๏ฎ = 1๏ป
๏ฎ
P
๏ฉ=
๏ฉ=1
(ii) Inductive step: Assume that
1
P
ยฏ
ยฏ
๏ฉ = 1 and ๏ฎ(๏ฎ+1)
ยฏ
2
๏ฉ=1
๏ฎ
P
๏ฉ=1
We need to show that then
๏ฎ+1
P
๏ฉ=1
๏ฎ+1
P
๏ฉ=1
๏ฉ=
๏ฎ
P
๏ฉ=1
๏ฉ = ๏ฎ(๏ฎ+1)
for every
2
๏ฎ=1
= 1(1+1)
= 1๏บ
2
๏ฉ = ๏ฎ(๏ฎ+1)
for a positive integer ๏ฎ๏บ
2
๏ฉ = (๏ฎ+1)(๏ฎ+2)
๏บ This is obtained as follows:
2
๏ฉ + (๏ฎ + 1) = ๏ฎ(๏ฎ+1)
+ (๏ฎ + 1) = ๏ฎ(๏ฎ+1)+2(๏ฎ+1)
= (๏ฎ+1)(๏ฎ+2)
๏บ
2
2
2
The young Gauss computed the sum
1 + 2 + ยท ยท ยท + 99 + 100
by noticing that it can be computed as the sum of 50 pairs, each with the
sum 101:
1 + 100 = 2 + 99 = ๏บ๏บ๏บ = 50 + 51 = 101๏บ
Hence the entire sum is equal to 50ยท101 = 5๏ป 050๏บ (The well-known historic
anecdote claims that his teacher gave this assignment to a class to keep
28
the class busy.) The Gauss idea can be easily generalized to an arbitrary
๏ฎ by adding
๏(๏ฎ) = 1 + 2 + ยท ยท ยท + (๏ฎ โ 1) + ๏ฎ
and
๏(๏ฎ) = ๏ฎ + (๏ฎ โ 1) + ยท ยท ยท + 2 + 1
to obtain
2๏(๏ฎ) = (๏ฎ + 1)๏ฎ and hence ๏(๏ฎ) =
๏ฎ(๏ฎ + 1)
๏บ
2
10. The object here is to compute (in oneโs head) the sum of the numbers in
the table below:
9 10
9 10 11
9 10 11
9 10 11
1 2 3
2 3
3
9 10 11
9 10 11
9 10 11
9 10 11
9 10 11
17
17 18
17 18 19
10 11
The first method is based on the observation that the sum of any two numbers in the squares symmetric with respect to the diagonal connecting the
lower left and upper right corners is equal to 20: 1+19, 2+18, 2+18, and
so on. So, since there are (10ยท10-10)/2 = 45 such pairs (we subtracted
the number of the squares on that diagonal from the total number of
squares), the sum of the numbers outside that diagonal is equal to 20ยท45
= 900. With 10ยท10 = 100 on the diagonal, the total sum is equal to 900
+ 100 = 1000.
The second method computes the sum row by row (or column by column).
The sum in the first row is equal to 10ยท11/2 = 55 according to formula
(S2). The sum of the numbers in second row is 55 + 10 since each of the
numbers is larger by 1 than their counterparts in the row above. The
same is true for all the other rows as well. Hence the total sum is equal
to 55 + (55+10) + (55+20) + …+ (55+90) = 55ยท10 + (10+20+…+90) =
29
55ยท10 + 10ยท(1+2+…+9) = 55ยท10 + 10ยท45 =1000.
Note that the first method uses the same trick Carl Gauss presumably
used to find the sum of the first hundred integers (Problem 9 in Exercises
2.3). We also used this formula (twice, in fact) in the second solution to
the problem.
11. a. The number of multiplications ๏ (๏ฎ) and the number of divisions ๏(๏ฎ)
made by the algorithm are given by the same sum:
๏ (๏ฎ) = ๏(๏ฎ) =
๏ฎโ2
X ๏ฎโ1
X
๏ฎ
X
1=
๏ฉ=0 ๏ช=๏ฉ+1 ๏ซ=๏ฉ
=
๏ฎโ2
X
๏ฉ=0
๏ฎโ2
X ๏ฎโ1
X
๏ฉ=0 ๏ช=๏ฉ+1
(๏ฎ โ ๏ฉ + 1) =
(๏ฎ โ ๏ฉ + 1)(๏ฎ โ 1 โ (๏ฉ + 1) + 1) =
๏ฎโ2
X
๏ฉ=0
(๏ฎ โ ๏ฉ + 1)(๏ฎ โ ๏ฉ โ 1)
= (๏ฎ + 1)(๏ฎ โ 1) + ๏ฎ(๏ฎ โ 2) + ๏บ๏บ๏บ + 3 โ 1
๏ฎโ1
๏ฎโ1
๏ฎโ1
X
X
X
(๏ฎ โ 1)๏ฎ(2๏ฎ โ 1)
(๏ฎ โ 1)๏ฎ
(๏ช + 2)๏ช =
๏ช2 +
2๏ช =
=
+2
6
2
๏ช=1
๏ช=1
๏ช=1
=
๏ฎ(๏ฎ โ 1)(2๏ฎ + 5)
1
โ ๏ฎ3 โ ฮ(๏ฎ3 )๏บ
6
3
b. The ine๏ฌciency is the repeated evaluation of the ratio ๏[๏ช๏ป ๏ฉ] ๏ฝ ๏[๏ฉ๏ป ๏ฉ]
in the algorithmโs innermost loop, which, in fact, does not change with
the loop variable ๏ซ๏บ Hence, this loop invariant can be computed just once
before entering this loop: ๏ด๏ฅ๏ญ๏ฐ โ ๏[๏ช๏ป ๏ฉ] ๏ฝ ๏[๏ฉ๏ป ๏ฉ]; the innermost loop is
then changed to
๏[๏ช๏ป ๏ซ] โ ๏[๏ช๏ป ๏ซ] โ ๏[๏ฉ๏ป ๏ซ] โ ๏ด๏ฅ๏ญ๏ฐ๏บ
This change eliminates the most expensive operation of the algorithm, the
division, from its innermost loop. The running time gain obtained by this
change can be estimated as follows:
๏ฃ๏ 31 ๏ฎ3 + ๏ฃ๏ 31 ๏ฎ3
๏๏ฏ๏ฌ๏ค (๏ฎ)
๏ฃ๏ + ๏ฃ๏
๏ฃ๏
=
=
+ 1๏ป
โ
๏๏ฎ๏ฅ๏ท (๏ฎ)
๏ฃ๏
๏ฃ๏
๏ฃ๏ 13 ๏ฎ3
where ๏ฃ๏ and ๏ฃ๏ are the time for one division and one multiplication,
respectively.
12. The answer can be obtained by a straightforward evaluation of the sum
2
๏ฎ
X
(2๏ฉ โ 1) + (2๏ฎ + 1) = 2๏ฎ2 + 2๏ฎ + 1๏บ
๏ฉ=1
30
(One can also get the closed-form answer by noting that the cells on the alternating diagonals of the von Neumann neighborhood of range ๏ฎ compose
two squares of sizes ๏ฎ + 1 and ๏ฎ, respectively.)
13. Let ๏(๏ฎ) be the total number of decimal digits in the first ๏ฎ positive
integers (book pages). The first nine numbers are one-digit, therefore
๏(๏ฎ) = ๏ฎ for 1 โค ๏ฎ โค 9๏บ The next 90 numbers from 10 to 99 inclusive are
two-digits. Hence
๏(๏ฎ) = 9 + 2(๏ฎ โ 9) for 10 โค ๏ฎ โค 99๏บ
The maximal value of ๏(๏ฎ) for this range is ๏(99) = 189๏บ Further, there
are 900 three-digit decimals, which leads to the formula
๏(๏ฎ) = 189 + 3(๏ฎ โ 99) for 100 โค ๏ฎ โค 999๏บ
The maximal value of ๏(๏ฎ) for this range is ๏(999) = 2889๏บ Adding four
digits for page 1000, we obtain ๏(1000) = 2893๏บ
31
Exercises 2.4
1. Solve the following recurrence relations.
a. ๏ธ(๏ฎ) = ๏ธ(๏ฎ โ 1) + 5 for ๏ฎ ๏พ 1๏ป
b. ๏ธ(๏ฎ) = 3๏ธ(๏ฎ โ 1) for ๏ฎ ๏พ 1๏ป
๏ธ(1) = 0
๏ธ(1) = 4
c. ๏ธ(๏ฎ) = ๏ธ(๏ฎ โ 1) + ๏ฎ for ๏ฎ ๏พ 0๏ป
๏ธ(0) = 0
d. ๏ธ(๏ฎ) = ๏ธ(๏ฎ๏ฝ2) + ๏ฎ for ๏ฎ ๏พ 1๏ป
๏ธ(1) = 1 (solve for ๏ฎ = 2๏ซ )
e. ๏ธ(๏ฎ) = ๏ธ(๏ฎ๏ฝ3) + 1 for ๏ฎ ๏พ 1๏ป
๏ธ(1) = 1 (solve for ๏ฎ = 3๏ซ )
2. Set up and solve a recurrence relation for the number of calls made by
F (๏ฎ)๏ป the recursive algorithm for computing ๏ฎ!๏บ
3. Consider the following recursive algorithm for computing the sum of the
first ๏ฎ cubes: ๏(๏ฎ) = 13 + 23 + ยท ยท ยท + ๏ฎ3 ๏บ
Algorithm ๏(๏ฎ)
//Input: A positive integer ๏ฎ
//Output: The sum of the first ๏ฎ cubes
if ๏ฎ = 1 return 1
else return ๏(๏ฎ โ 1) + ๏ฎ โ ๏ฎ โ ๏ฎ
a. Set up and solve a recurrence relation for the number of times the
algorithmโs basic operation is executed.
b. How does this algorithm compare with the straightforward nonrecursive
algorithm for computing this function?
4. Consider the following recursive algorithm.
Algorithm ๏(๏ฎ)
//Input: A positive integer ๏ฎ
if ๏ฎ = 1 return 1
else return ๏(๏ฎ โ 1) + 2 โ ๏ฎ โ 1
a. Set up a recurrence relation for this functionโs values and solve it
to determine 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.
32
5. Tower of Hanoi a. In the original version of the Tower of Hanoi puzzle,
as it was published by Edouard Lucas, a French mathematician, in the
1890s, 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 ๏ฉth largest disk (1 โค ๏ฉ โค ๏ฎ) in
this algorithm?
c. Find a nonrecursive algorithm for the Tower of Hanoi puzzle and implement it in the language of your choice.
6. B Restricted Tower of Hanoi Consider the version of the Tower of Hanoi
puzzle in which ๏ฎ 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.
7. B a. Prove that the exact number of additions made by the recursive
algorithm BinRec( ๏ฎ) for an arbitrary positive integer ๏ฎ is blog2 ๏ฎc๏บ
b. Set up a recurrence relation for the number of additions made by
the nonrecursive version of this algorithm (see Section 2.3, Example 4)
and solve it.
8. a. Design a recursive algorithm for computing 2๏ฎ for any nonnegative
integer ๏ฎ that is based on the formula: 2๏ฎ = 2๏ฎโ1 + 2๏ฎโ1 ๏บ
b. Set up a recurrence relation for the number of additions made by
the algorithm and solve it.
c. Draw a tree of recursive calls for this algorithm and count the number
of calls made by the algorithm.
d. Is it a good algorithm for solving this problem?
9. Consider the following recursive algorithm.
Algorithm Riddle(๏[0๏บ๏บ๏ฎ โ 1])
//Input: An array ๏[0๏บ๏บ๏ฎ โ 1] of real numbers
if ๏ฎ = 1 return ๏[0]
else temp โ Riddle(๏[0๏บ๏บ๏ฎ โ 2])
if temp โค ๏[๏ฎ โ 1] return temp
else return ๏[๏ฎ โ 1]
a. What does this algorithm compute?
33
b. Set up a recurrence relation for the algorithmโs basic operation count and
solve it.
10. Consider the following algorithm to check whether a graph defined by its
adjacency matrix is complete.
Algorithm GraphComplete(๏[0๏บ๏บ๏ฎ โ 1๏ป 0๏บ๏บ๏ฎ โ 1])
//Input: Adjacency matrix ๏[0๏บ๏บ๏ฎ โ 1๏ป 0๏บ๏บ๏ฎ โ 1]) of an undirected graph ๏
with ๏ฎ โฅ 1 vertices
//Output: 1 (true) if ๏ is complete and 0 (false) otherwise
if ๏ฎ = 1 return 1
//one-vertex graph is complete by definition
else
if not GraphComplete(๏[0๏บ๏บ๏ฎ โ 2๏ป 0๏บ๏บ๏ฎ โ 2]) return 0
else for ๏ช โ 0 to ๏ฎ โ 2 do
if ๏[๏ฎ โ 1๏ป ๏ช] = 0 return 0
return 1
What is the algorithmโs e๏ฌciency class in the worst case?
11. The determinant of an ๏ฎ ร ๏ฎ matrix
โก
๏ก0 0
โข ๏ก1 0
โข
๏=โข
..
โฃ
.
๏ก๏ฎโ1 0
๏ก0 ๏ฎโ1
๏ก1 ๏ฎโ1
๏ก๏ฎโ1 ๏ฎโ1
โค
โฅ
โฅ
โฅ๏ป
โฆ
denoted det ๏๏ป can be defined as ๏ก00 for ๏ฎ = 1 and, for ๏ฎ ๏พ 1๏ป by the
recursive formula
๏ฎโ1
X
det ๏ =
๏ณ๏ช ๏ก0 ๏ช det ๏๏ช ๏ป
๏ช=0
where ๏ณ๏ช is +1 if ๏ช is even and โ1 if ๏ช is odd, ๏ก0 ๏ช is the element in row 0
and column ๏ช, and ๏๏ช is the (๏ฎ โ 1) ร (๏ฎ โ 1) matrix obtained from matrix
๏ by deleting its row 0 and column ๏ช.
a.B Set up a recurrence relation for the number of multiplications made
by the algorithm implementing this recursive definition.
b.B Without solving the recurrence, what can you say about the solutionโs order of growth as compared to ๏ฎ! ?
12. von Neumannโs neighborhood revisited Find the number of cells in the
von Neumann neighborhood of range ๏ฎ (Problem 12 in Exercises 2.3) by
setting up and solving a recurrence relation.
34
13. Frying hamburgers There are ๏ฎ hamburgers to be fried on a small grill
that can hold only two hamburgers at a time. Each hamburger has to be
fried on both sides; frying one side of a hamburger takes one minute, regardless of whether one or two hamburgers are fried at the same time.
Consider the following recursive algorithm for executing this task. If
๏ฎ โค 2๏ป fry the hamburger (or the two hamburgers together if ๏ฎ = 2)
on each side. If ๏ฎ ๏พ 2๏ป fry two hamburgers together on each side and then
fry the remaining ๏ฎ โ 2 hamburgers by the same algorithm.
a. Set up and solve the recurrence for the amount of time this algorithm needs to fry ๏ฎ hamburgers.
b. Explain why this algorithm does not fry the hamburgers in the minimum amount of time for all ๏ฎ ๏พ 0.
c. Give a correct recursive algorithm that executes the task in the minimum amount of time for all ๏ฎ ๏พ 0 and find a closed-form formula for the
minimum amount of time.
14. B Celebrity problem A celebrity among a group of ๏ฎ people is a person
who knows nobody but is known by everybody else. The task is to
identify a celebrity by only asking questions to people of the form: “Do
you know him/her?” Design an e๏ฌcient algorithm to identify a celebrity
or determine that the group has no such person. How many questions
does your algorithm need in the worst case? [Man89]
35
Hints to Exercises 2.4
1. Each of these recurrences can be solved by the method of backward substitutions.
2. The recurrence relation in question is almost identical to the recurrence
relation for the number of multiplications, which was set up and solved in
the section.
3. a. The question is similar to that about the e๏ฌciency of the recursive
algorithm for computing ๏ฎ!๏บ
b. Write a pseudocode for the nonrecursive algorithm and determine its
e๏ฌciency.
4. a. Note that you are asked here about a recurrence for the functionโs
values, not about a recurrence for the number of times its operation is
executed. Just follow the pseudocode to set it up. It is easier to solve this
recurrence by forward substitutions (see Appendix B).
b. This question is very similar to one we have already discussed.
c. You may want to include the substraction needed to decrease ๏ฎ๏บ
5. a. Use the formula for the number of disk moves derived in the section.
b. Solve the problem for 3 disks to investigate the number of moves made
by each of the disks. Then generalize the observations and prove their
validity for the general case of ๏ฎ disks.
6. The required algorithm and the method of its analysis are similar to those
of the classic version of the puzzle. Because of the additional constraint,
more than two smaller instances of the puzzle need to be solved here.
7. a. Consider separately the cases of even and odd values of ๏ฎ and show that
for both of them blog2 ๏ฎc satisfies the recurrence relation and its initial
condition.
b. Just follow the algorithmโs pseudocode.
8. a. Use the formula 2๏ฎ = 2๏ฎโ1 + 2๏ฎโ1 without simplifying it; do not forget
to provide a condition for stopping your recursive calls.
b. A similar algorithm was investigated in Section 2.4.
c. A similar question was investigated in Section 2.4.
d. A bad e๏ฌciency class of an algorithm by itself does not mean that
36
the algorithm is bad. For example, the classic algorithm for the Tower of
Hanoi puzzle is optimal despite its exponential-time e๏ฌciency. Therefore,
a claim that a particular algorithm is not good requires a reference to a
better one.
9. a. Tracing the algorithm for ๏ฎ = 1 and ๏ฎ = 2 should help.
b. It is very similar to one of the examples discussed in the section.
10. Get the basic operation count either by solving a recurrence relation or
by computing directly the number of the adjacency matix elements the
algorithm checks in the worst case.
11. a. Use the definitionโs formula to get the recurrence relation for the number of multiplications made by the algorithm.
b. Investigate the right-hand side of the recurrence relation. Computing
the first few values of ๏ (๏ฎ) may be helpful, too.
12. You might want to use the neighborhoodโs symmetry to obtain a simple
formula for the number of squares added to the neighborhood on the ๏ฎth
iteration of the algorithm.
13. The minimum amount of time needed to fry three hamburgers is smaller
than four minutes.
14. Solve first a simpler version in which a celebrity must be present.
37
Solutions to Exercises 2.4
1. a. ๏ธ(๏ฎ) = ๏ธ(๏ฎ โ 1) + 5 for ๏ฎ ๏พ 1๏ป ๏ธ(1) = 0
๏ธ(๏ฎ) =
=
=
=
=
=
=
๏ธ(๏ฎ โ 1) + 5
[๏ธ(๏ฎ โ 2) + 5] + 5 = ๏ธ(๏ฎ โ 2) + 5 ยท 2
[๏ธ(๏ฎ โ 3) + 5] + 5 ยท 2 = ๏ธ(๏ฎ โ 3) + 5 ยท 3
๏บ๏บ๏บ
๏ธ(๏ฎ โ ๏ฉ) + 5 ยท ๏ฉ
๏บ๏บ๏บ
๏ธ(1) + 5 ยท (๏ฎ โ 1) = 5(๏ฎ โ 1)๏บ
Note: The solution can also be obtained by using the formula for the ๏ฎ
term of the arithmetical progression:
๏ธ(๏ฎ) = ๏ธ(1) + ๏ค(๏ฎ โ 1) = 0 + 5(๏ฎ โ 1) = 5(๏ฎ โ 1)๏บ
b. ๏ธ(๏ฎ) = 3๏ธ(๏ฎ โ 1) for ๏ฎ ๏พ 1๏ป
๏ธ(๏ฎ) =
=
=
=
=
=
=
๏ธ(1) = 4
3๏ธ(๏ฎ โ 1)
3[3๏ธ(๏ฎ โ 2)] = 32 ๏ธ(๏ฎ โ 2)
32 [3๏ธ(๏ฎ โ 3)] = 33 ๏ธ(๏ฎ โ 3)
๏บ๏บ๏บ
3๏ฉ ๏ธ(๏ฎ โ ๏ฉ)
๏บ๏บ๏บ
3๏ฎโ1 ๏ธ(1) = 4 ยท 3๏ฎโ1 ๏บ
Note: The solution can also be obtained by using the formula for the ๏ฎ
term of the geometric progression:
๏ธ(๏ฎ) = ๏ธ(1)๏ฑ ๏ฎโ1 = 4 ยท 3๏ฎโ1 ๏บ
c. ๏ธ(๏ฎ) = ๏ธ(๏ฎ โ 1) + ๏ฎ for ๏ฎ ๏พ 0๏ป
๏ธ(๏ฎ) =
=
=
=
=
=
๏ธ(0) = 0
๏ธ(๏ฎ โ 1) + ๏ฎ
[๏ธ(๏ฎ โ 2) + (๏ฎ โ 1)] + ๏ฎ = ๏ธ(๏ฎ โ 2) + (๏ฎ โ 1) + ๏ฎ
[๏ธ(๏ฎ โ 3) + (๏ฎ โ 2)] + (๏ฎ โ 1) + ๏ฎ = ๏ธ(๏ฎ โ 3) + (๏ฎ โ 2) + (๏ฎ โ 1) + ๏ฎ
๏บ๏บ๏บ
๏ธ(๏ฎ โ ๏ฉ) + (๏ฎ โ ๏ฉ + 1) + (๏ฎ โ ๏ฉ + 2) + ยท ยท ยท + ๏ฎ
๏บ๏บ๏บ
๏ฎ(๏ฎ + 1)
= ๏ธ(0) + 1 + 2 + ยท ยท ยท + ๏ฎ =
๏บ
2
38
d. ๏ธ(๏ฎ) = ๏ธ(๏ฎ๏ฝ2) + ๏ฎ for ๏ฎ ๏พ 1๏ป
๏ธ(2๏ซ ) =
=
=
=
=
=
=
=
๏ธ(1) = 1 (solve for ๏ฎ = 2๏ซ )
๏ธ(2๏ซโ1 ) + 2๏ซ
[๏ธ(2๏ซโ2 ) + 2๏ซโ1 ] + 2๏ซ = ๏ธ(2๏ซโ2 ) + 2๏ซโ1 + 2๏ซ
[๏ธ(2๏ซโ3 ) + 2๏ซโ2 ] + 2๏ซโ1 + 2๏ซ = ๏ธ(2๏ซโ3 ) + 2๏ซโ2 + 2๏ซโ1 + 2๏ซ
๏บ๏บ๏บ
๏ธ(2๏ซโ๏ฉ ) + 2๏ซโ๏ฉ+1 + 2๏ซโ๏ฉ+2 + ยท ยท ยท + 2๏ซ
๏บ๏บ๏บ
๏ธ(2๏ซโ๏ซ ) + 21 + 22 + ยท ยท ยท + 2๏ซ = 1 + 21 + 22 + ยท ยท ยท + 2๏ซ
2๏ซ+1 โ 1 = 2 ยท 2๏ซ โ 1 = 2๏ฎ โ 1๏บ
e. ๏ธ(๏ฎ) = ๏ธ(๏ฎ๏ฝ3) + 1 for ๏ฎ ๏พ 1๏ป
๏ธ(3๏ซ ) =
=
=
=
=
=
=
2. ๏(๏ฎ) = ๏(๏ฎ โ 1) + 1๏ป
when ๏ฎ = 0)๏บ
๏ธ(1) = 1 (solve for ๏ฎ = 3๏ซ )
๏ธ(3๏ซโ1 ) + 1
[๏ธ(3๏ซโ2 ) + 1] + 1 = ๏ธ(3๏ซโ2 ) + 2
[๏ธ(3๏ซโ3 ) + 1] + 2 = ๏ธ(3๏ซโ3 ) + 3
๏บ๏บ๏บ
๏ธ(3๏ซโ๏ฉ ) + ๏ฉ
๏บ๏บ๏บ
๏ธ(3๏ซโ๏ซ ) + ๏ซ = ๏ธ(1) + ๏ซ = 1 + log3 ๏ฎ๏บ
๏(0) = 1 (there is a call but no multiplications
๏(๏ฎ) = ๏(๏ฎ โ 1) + 1 = [๏(๏ฎ โ 2) + 1] + 1 = ๏(๏ฎ โ 2) + 2 = ๏บ๏บ๏บ
= ๏(๏ฎ โ ๏ฉ) + ๏ฉ = ๏บ๏บ๏บ = ๏(0) + ๏ฎ = 1 + ๏ฎ๏บ
3. a. Let ๏ (๏ฎ) be the number of multiplications made by the algorithm.
We have the following recurrence relation for it:
๏ (๏ฎ) = ๏ (๏ฎ โ 1) + 2๏ป
39
๏ (1) = 0๏บ
We can solve it by backward substitutions:
๏ (๏ฎ) =
=
=
=
=
=
=
๏ (๏ฎ โ 1) + 2
[๏ (๏ฎ โ 2) + 2] + 2 = ๏ (๏ฎ โ 2) + 2 + 2
[๏ (๏ฎ โ 3) + 2] + 2 + 2 = ๏ (๏ฎ โ 3) + 2 + 2 + 2
๏บ๏บ๏บ
๏ (๏ฎ โ ๏ฉ) + 2๏ฉ
๏บ๏บ๏บ
๏ (1) + 2(๏ฎ โ 1) = 2(๏ฎ โ 1)๏บ
b. Here is a pseudocode for the nonrecursive option:
Algorithm NonrecS (๏ฎ)
//Computes the sum of the first ๏ฎ cubes nonrecursively
//Input: A positive integer ๏ฎ
//Output: The sum of the first ๏ฎ cubes.
๏โ1
for ๏ฉ โ 2 to ๏ฎ do
๏ โ๏+๏ฉโ๏ฉโ๏ฉ
return ๏
The number of multiplications made by this algorithm will be
๏ฎ
X
๏ฉ=2
2=2
๏ฎ
X
๏ฉ=2
1 = 2(๏ฎ โ 1)๏บ
This is exactly the same number as in the recursive version, but the nonrecursive version doesnโt carry the time and space overhead associated with
the recursionโs stack.
4. a. ๏(๏ฎ) = ๏(๏ฎ โ 1) + 2๏ฎ โ 1 for ๏ฎ ๏พ 1๏ป
๏(1) = 1๏บ
Computing the first few terms of the sequence yields the following:
๏(2) = ๏(1) + 2 ยท 2 โ 1 = 1 + 2 ยท 2 โ 1 = 4;
๏(3) = ๏(2) + 2 ยท 3 โ 1 = 4 + 2 ยท 3 โ 1 = 9;
๏(4) = ๏(3) + 2 ยท 4 โ 1 = 9 + 2 ยท 4 โ 1 = 16๏บ
Thus, it appears that ๏(๏ฎ) = ๏ฎ2 ๏บ Weโll check this hypothesis by substituting this formula into the recurrence equation and the initial condition.
The left hand side yields ๏(๏ฎ) = ๏ฎ2 ๏บ The right hand side yields
๏(๏ฎ โ 1) + 2๏ฎ โ 1 = (๏ฎ โ 1)2 + 2๏ฎ โ 1 = ๏ฎ2 ๏บ
40
The initial condition is verified immediately: ๏(1) = 12 = 1๏บ
b. ๏ (๏ฎ) = ๏ (๏ฎ โ 1) + 1 for ๏ฎ ๏พ 1๏ป ๏ (1) = 0๏บ Solving 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 arithmetical progression yields ๏ (๏ฎ) = ๏ฎ โ 1๏บ
c. Let ๏(๏ฎ) be the number of additions and subtractions made by the
algorithm. The recurrence for ๏(๏ฎ) is ๏(๏ฎ) = ๏(๏ฎ โ 1) + 3 for ๏ฎ ๏พ 1๏ป
๏(1) = 0๏บ Solving it by backward substitutions or by applying the formula
for the ๏ฎth term of an arithmetical progression yields ๏(๏ฎ) = 3(๏ฎ โ 1)๏บ
Note: If we donโt include in the count the subtractions needed to decrease ๏ฎ๏ป the recurrence will be ๏(๏ฎ) = ๏(๏ฎ โ 1) + 2 for ๏ฎ ๏พ 1๏ป ๏(1) = 0๏บ
Its solution is ๏(๏ฎ) = 2(๏ฎ โ 1)๏บ
5. a. The number of moves is given by the formula: ๏ (๏ฎ) = 2๏ฎ โ 1๏บ Hence
264 โ 1
โ 3๏บ5 ยท 1013 years
60 ยท 24 ยท 365
vs. the age of the Universe estimated to be about 13 ยท 109 years.
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
smaller tower is moved on the top of it (this again requires one move of
the (๏ฉ + 1)st disk). Thus, for each move of the ๏ฉth disk, the algorithm
moves the (๏ฉ + 1)st disk exactly twice. Since for ๏ฉ = 1, the number of
moves is equal to 1, we have the following recurrence for the number of
moves made by the ๏ฉth disk:
๏ญ(๏ฉ + 1) = 2๏ญ(๏ฉ) for 1 โค ๏ฉ ๏ผ ๏ฎ๏ป
๏ญ(1) = 1๏บ
Its solution is ๏ญ(๏ฉ) = 2๏ฉโ1 for ๏ฉ = 1๏ป 2๏ป ๏บ๏บ๏บ๏ป ๏ฎ๏บ (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:
๏ (๏ฎ) =
๏ฎ
X
๏ฉ=1
๏ญ(๏ฉ) =
๏ฎ
X
๏ฉ=1
2๏ฉโ1 = 1 + 2 + ยท ยท ยท + 2๏ฎโ1 = 2๏ฎ โ 1๏บ
6. If ๏ฎ = 1๏ป move the single disk from peg A first to peg B and then from
peg B to peg C. If ๏ฎ ๏พ 1๏ป do the following:
transfer recursively the top ๏ฎ โ 1 disks from peg A to peg C through peg
B
41
move the disk from peg A to peg B
transfer recursively ๏ฎ โ 1 disks from peg C to peg A through peg B
move the disk from peg B to peg C
transfer recursively ๏ฎ โ 1 disks from peg A to peg C through peg B.
The recurrence relation for the number of moves ๏ (๏ฎ) is
๏ (๏ฎ) = 3๏ (๏ฎ โ 1) + 2 for ๏ฎ ๏พ 1๏ป ๏ (1) = 2๏บ
It can be solved by backward substitutions as follows
๏ (๏ฎ) =
=
=
=
=
=
=
3๏ (๏ฎ โ 1) + 2
3[3๏ (๏ฎ โ 2) + 2] + 2 = 32 ๏ (๏ฎ โ 2) + 3 ยท 2 + 2
32 [3๏ (๏ฎ โ 3) + 2] + 3 ยท 2 + 2 = 33 ๏ (๏ฎ โ 3) + 32 ยท 2 + 3 ยท 2 + 2
๏บ๏บ๏บ
3๏ฉ ๏ (๏ฎ โ ๏ฉ) + 2(3๏ฉโ1 + 3๏ฉโ2 + ยท ยท ยท + 1) = 3๏ฉ ๏ (๏ฎ โ ๏ฉ) + 3๏ฉ โ 1
๏บ๏บ๏บ
3๏ฎโ1 ๏ (1) + 3๏ฎโ1 โ 1 = 3๏ฎโ1 ยท 2 + 3๏ฎโ1 โ 1 = 3๏ฎ โ 1๏บ
7. a. Weโll verify by substitution that ๏(๏ฎ) = blog2 ๏ฎc satisfies the recurrence
for the number of additions
๏(๏ฎ) = ๏(b๏ฎ๏ฝ2c) + 1 for every ๏ฎ ๏พ 1๏บ
Let ๏ฎ be even, i.e., ๏ฎ = 2๏ซ๏บ
The left-hand side is:
๏(๏ฎ) = blog2 ๏ฎc = blog2 2๏ซc = blog2 2 + log2 ๏ซc = (1 + blog2 ๏ซc) =
blog2 ๏ซc + 1๏บ
The right-hand side is:
๏(b๏ฎ๏ฝ2c) + 1 = ๏(b2๏ซ๏ฝ2c) + 1 = ๏(๏ซ) + 1 = blog2 ๏ซc + 1๏บ
Let ๏ฎ be odd, i.e., ๏ฎ = 2๏ซ + 1๏บ
The left-hand side is:
๏(๏ฎ) = blog2 ๏ฎc = blog2 (2๏ซ + 1)c = using blog2 ๏ธc = dlog2 (๏ธ + 1)e โ 1
dlog2 (2๏ซ + 2)e โ 1 = dlog2 2(๏ซ + 1)e โ 1
= dlog2 2 + log2 (๏ซ + 1)e โ 1 = 1 + dlog2 (๏ซ + 1)e โ 1 = blog2 ๏ซc + 1๏บ
The right-hand side is:
๏(b๏ฎ๏ฝ2c) + 1 = ๏(b(2๏ซ + 1)๏ฝ2c) + 1 = ๏(b๏ซ + 1๏ฝ2c) + 1 = ๏(๏ซ) + 1 =
blog2 ๏ซc + 1๏บ
The initial condition is verified immediately: ๏(1) = blog2 1c = 0๏บ
42
b. The recurrence relation for the number of additions is identical to
the one for the recursive version:
๏(๏ฎ) = ๏(b๏ฎ๏ฝ2c) + 1 for ๏ฎ ๏พ 1๏ป
๏(1) = 0๏ป
with the solution ๏(๏ฎ) = blog2 ๏ฎc + 1.
8. a. Algorithm Power (๏ฎ)
//Computes 2๏ฎ recursively by the formula 2๏ฎ = 2๏ฎโ1 + 2๏ฎโ1
//Input: A nonnegative integer ๏ฎ
//Output: Returns 2๏ฎ
if ๏ฎ = 0 return 1
else return ๏ ๏ฏ๏ท๏ฅ๏ฒ(๏ฎ โ 1) + ๏ ๏ฏ๏ท๏ฅ๏ฒ(๏ฎ โ 1)
b. ๏(๏ฎ) = 2๏(๏ฎ โ 1) + 1๏ป ๏(0) = 0๏บ
๏(๏ฎ) =
=
=
=
=
=
=
2๏(๏ฎ โ 1) + 1
2[2๏(๏ฎ โ 2) + 1] + 1 = 22 ๏(๏ฎ โ 2) + 2 + 1
22 [2๏(๏ฎ โ 3) + 1] + 2 + 1 = 23 ๏(๏ฎ โ 3) + 22 + 2 + 1
๏บ๏บ๏บ
2๏ฉ ๏(๏ฎ โ ๏ฉ) + 2๏ฉโ1 + 2๏ฉโ2 + ยท ยท ยท + 1
๏บ๏บ๏บ
2๏ฎ ๏(0) + 2๏ฎโ1 + 2๏ฎโ2 + ยท ยท ยท + 1 = 2๏ฎโ1 + 2๏ฎโ2 + ยท ยท ยท + 1 = 2๏ฎ โ 1๏บ
c. The tree of recursive calls for this algorithm looks as follows:
n
n-1
n-1
n-2
1
0
…
0
n-2
n-2
…
…
1
0
n-2
0
1
0
Note that it has one extra level compared to the similar tree for the Tower
of Hanoi puzzle.
d. Itโs a very bad algorithm because it is vastly inferior to the algorithm that simply multiplies an accumulator by 2 ๏ฎ times, not to mention
much more e๏ฌcient algorithms discussed later in the book. Even if only
additions are allowed, adding two 2๏ฎโ1 times is better than this algorithm.
43
1
0
0
0
9. a. The algorithm computes the value of the smallest element in a given
array.
b. The recurrence for the number of key comparisons is
๏(๏ฎ) = ๏(๏ฎ โ 1) + 1 for ๏ฎ ๏พ 1๏ป
๏(1) = 0๏บ
Solving it by backward substitutions yields ๏(๏ฎ) = ๏ฎ โ 1๏บ
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) + ๏ฎ โ 1 for ๏ฎ ๏พ 1๏ป
๏(1) = 0๏บ
Solving the recurrence by backward substitutions yields the following:
๏๏ท (๏ฎ) =
=
=
=
=
=
=
๏๏ท (๏ฎ โ 1) + ๏ฎ โ 1
[๏๏ท (๏ฎ โ 2) + ๏ฎ โ 2] + ๏ฎ โ 1
[๏๏ท (๏ฎ โ 3) + ๏ฎ โ 3] + ๏ฎ โ 2 + ๏ฎ โ 1
๏บ๏บ๏บ
๏๏ท (๏ฎ โ ๏ฉ) + (๏ฎ โ ๏ฉ) + (๏ฎ โ ๏ฉ + 1) + ยท ยท ยท + (๏ฎ โ 1)
๏บ๏บ๏บ
๏๏ท (1) + 1 + 2 + ยท ยท ยท + (๏ฎ โ 1) = 0 + (๏ฎ โ 1)๏ฎ๏ฝ2 = (๏ฎ โ 1)๏ฎ๏ฝ2๏บ
This result could also be obtained directly by observing that in the worst
case the algorithm checks every element below the main diagonal of the
adjacency matrix of a given graph.
11. a. Let ๏ (๏ฎ) be the number of multiplications made by the algorithm
P๏ฎโ1
based on the formula det ๏ =
๏ช=0 ๏ณ๏ช ๏ก0๏ช det ๏๏ช ๏บ If we donโt include
multiplications by ๏ณ๏ช , which are just ยฑ1๏ป then
๏ (๏ฎ) =
๏ฎโ1
X
๏ช=0
(๏ (๏ฎ โ 1) + 1)๏ป
i.e.,
๏ (๏ฎ) = ๏ฎ(๏ (๏ฎ โ 1) + 1) for ๏ฎ ๏พ 1 and ๏ (1) = 0๏บ
b. Since ๏ (๏ฎ) = ๏ฎ๏ (๏ฎ โ 1) + ๏ฎ๏ป the sequence ๏ (๏ฎ) grows to infinity at
least as fast as the factorial function defined by ๏ (๏ฎ) = ๏ฎ๏ (๏ฎ โ 1)๏บ
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
we obtain the following recurrence for ๏(๏ฎ)๏ป the total number of squares
in the neighborhood after the ๏ฎth iteration:
๏(๏ฎ) = ๏(๏ฎ โ 1) + 4๏ฎ for ๏ฎ ๏พ 0 and ๏(0) = 1๏บ
Solving the recurrence by backward substitutions yields the following:
๏(๏ฎ) =
=
=
=
=
=
=
=
๏(๏ฎ โ 1) + 4๏ฎ
[๏(๏ฎ โ 2) + 4(๏ฎ โ 1)] + 4๏ฎ = ๏(๏ฎ โ 2) + 4(๏ฎ โ 1) + 4๏ฎ
[๏(๏ฎ โ 3) + 4(๏ฎ โ 2)] + 4(๏ฎ โ 1) + 4๏ฎ = ๏(๏ฎ โ 3) + 4(๏ฎ โ 2) + 4(๏ฎ โ 1) + 4๏ฎ
๏บ๏บ๏บ
๏(๏ฎ โ ๏ฉ) + 4(๏ฎ โ ๏ฉ + 1) + 4(๏ฎ โ ๏ฉ + 2) + ยท ยท ยท + 4๏ฎ
๏บ๏บ๏บ
๏(0) + 4 ยท 1 + 4 ยท 2 + ยท ยท ยท + 4๏ฎ = 1 + 4(1 + 2 + ยท ยท ยท + ๏ฎ)
1 + 4๏ฎ(๏ฎ + 1)๏ฝ2 = 2๏ฎ2 + 2๏ฎ + 1๏บ
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๏บ
Its solution is ๏ (๏ฎ) = ๏ฎ for every even ๏ฎ ๏พ 0 and ๏ (๏ฎ) = ๏ฎ + 1 for every
odd ๏ฎ ๏พ 0 can be obtained either by backward substitutitons or by applying the formula for the generic term of an arithmetical progression.
b. The algorithm fails to execute the task of frying ๏ฎ hamburgers in the
minimum amount of time for any odd ๏ฎ ๏พ 1. In particular, it requires
๏ (3) = 4 minutes to fry three hamburgers, whereas one can do this in 3
minutes: First, fry pancakes 1 and 2 on one side. Then fry pancake 1 on
the second side together with pancake 3 on its first side. Finally, fry both
pancakes 2 and 3 on the second side.
c. If ๏ฎ โค 2๏ป fry the hamburger (or the two hamburgers together if ๏ฎ = 2)
on each side. If ๏ฎ = 3๏ป fry the pancakes in 3 minutes as indicated in the
answer to the part b question. If ๏ฎ ๏พ 3๏ป fry two hamburgers together
on each side and then fry the remaining ๏ฎ โ 2 hamburgers by the same
algorithm. The recurrence for the number of minutes needed to fry ๏ฎ
hamburgers looks now as follows:
๏ (๏ฎ) = ๏ (๏ฎ โ 2) + 2 for ๏ฎ ๏พ 3๏ป
๏ (1) = 2๏ป ๏ (2) = 2๏ป ๏ (3) = 3๏บ
For every ๏ฎ ๏พ 1๏ป this algorithm requires ๏ฎ minutes to do the job. This is
the minimum time possible because ๏ฎ pancakes have 2๏ฎ sides to be fried
45
and any algorithm can fry no more than two sides in one minute. The
algorithm is also obviously optimal for the trivial case of ๏ฎ = 1๏ป requiring
two minutes to fry a single hamburger on both sides.
Note: The case of ๏ฎ = 3 is a well-known puzzle, which dates back at
least to 1943. Its algorithmic version for an arbitrary ๏ฎ is included in Algorithmic Puzzles by A. Levitin and M. Levitin, Oxford University Press,
2011, Problem 16.
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 ๏ฎ โ 1 people
recursively, and then verify the returned solution by asking no more than
two questions. Here is a more detailed description of this algorithm:
If ๏ฎ = 1๏ป return that one person as a celebrity. If ๏ฎ ๏พ 1๏ป proceed as
follows:
Step 1 Select two people from the group given, say, A and B, and ask A whether
A knows B. If A knows B, remove A from the remaining people who can
be a celebrity; if A doesnโt know B, remove B from this group.
Step 2 Solve the problem recursively for the remaining group of ๏ฎ โ 1 people
who can be a celebrity.
Step 3 If the solution returned in Step 2 indicates that there is no celebrity
among the group of ๏ฎ โ 1 people, 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
in Step 1 and, if the answer is no, whether the person removed in Step
1 knows C. If the answer to the second question is yes,” return C as a
celebrity and “no celebrity” otherwise. If Step 2 identified B as a celebrity,
just ask whether B knows A: return B as a celebrity if the answer is no
and “no celebrity” otherwise. If Step 2 identified A as a celebrity, ask
whether B knows A: return A as a celebrity if the answer is yes and “no
celebrity” otherwise.
The recurrence for ๏(๏ฎ), the number of questions needed in the worst case,
is as follows:
๏(๏ฎ) = ๏(๏ฎ โ 1) + 3 for ๏ฎ ๏พ 2๏ป
๏(2) = 2๏ป
๏(1) = 0๏บ
Its solution is ๏(๏ฎ) = 2 + 3(๏ฎ โ 2) for ๏ฎ ๏พ 1 and ๏(1) = 0๏บ
Note: A discussion of this problem, including an implementation of this algorithm in a Pascal-like pseudocode, can be found in Udi Manberโs Introduction
to Algorithms: A Creative Approach. Addison-Wesley, 1989.
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 surrounded by a wall. How many pairs of rabbits will be there in a year if the
initial pair of rabbits (male and female) are newborn, and all rabbit pairs
are not fertile during their first month of life but thereafter give birth to
one new male/female pair at the end of every month?
3. Climbing stairs Find the number of di๏ฌerent ways to climb an ๏ฎ-stair
staircase if each step is either or two stairs. For example, a 3-stair staircase
can be climbed three ways: 1-1-1, 1-2, and 2-1.
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 โ15 (๏๏ฎ โ๏ฬ ) 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
and 263 โ 1, respectively. Find the smallest ๏ฎ for which the ๏ฎth Fibonacci
number is not going to fit in a memory allocated for
a. the type int.
b. the type long.
7. Consider the recursive definition-based algorithm for computing the ๏ฎth
Fibonacci number ๏ (๏ฎ). Let ๏(๏ฎ) and ๏(๏ฎ) be the number of times ๏ (1)
and ๏ (0)๏ป respectively, are computed. Prove that
a. ๏(๏ฎ) = ๏ (๏ฎ)๏บ
b. ๏(๏ฎ) = ๏ (๏ฎ โ 1)๏บ
8. Improve algorithm ๏ ๏ฉ๏ข of the text so that it requires only ฮ(1) space.
9. Prove the equality
โ
ยธ โ
ยธ๏ฎ
๏ (๏ฎ โ 1)
๏ (๏ฎ)
0 1
=
๏ (๏ฎ)
๏ (๏ฎ + 1)
1 1
for ๏ฎ โฅ 1๏บ
10. B How many modulo divisions are made by Euclidโs algorithm on two
consecutive Fibonacci numbers ๏ (๏ฎ) and ๏ (๏ฎ โ 1) as the algorithmโs input?
11. Dissecting a Fibonacci rectangle Given a rectangle whose sides are two
consecutive Fibonacci numbers, design an algorithm to dissect it into
squares with no more than two of the squares be of the same size. What
is the time e๏ฌciency class of your algorithm?
47
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)
the recursive definition-based algorithm F (n); (b) the iterative definitionbased algorithm Fib(n). Perform an experiment to find the largest value
of ๏ฎ for which your programs run under 1 minute on your computer.
48
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.
3. There are several ways to solve this problem. The most elegant of them
makes it possible to put the problem in this section.
4. Writing down the first, say, ten Fibonacci numbers makes the pattern
obvious.
๏ฎ
5. It is easier to substitute ๏๏ฎ and ๏ฬ into the recurrence equation separately๏บ
Why will this su๏ฌce?
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.
9. Prove it by mathematical induction.
10. Consider first a small example such as computing gcd(13๏ป 8).
11. Take advantage of the special nature of the rectangleโs dimensions.
12. The last ๏ซ digits of an integer ๏ can be obtained by computing ๏ mod 10๏ซ ๏บ
Performing all operations of your algorithms modulo 10๏ซ (see Appendix
A) will enable you to circumvent the exponential growth of the Fibonacci
numbers. Also note that Section 2.6 is devoted to a general discussion of
the empirical analysis of algorithms.
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),
plus the number of rabbit pairs born at the end of month ๏ฎ, which is
according to the problemโs assumptions is equal to ๏(๏ฎ โ 2), the number
of rabbit pairs at the end of month ๏ฎ โ 2. Thus, we have the recurrence
relation
๏(๏ฎ) = ๏(๏ฎ โ 1) + ๏(๏ฎ โ 2) for ๏ฎ ๏พ 1๏ป ๏(0) = 1๏ป ๏(1) = 1๏บ
The following table gives the values of the first thirteen terms of the sequence, called the Fibonacci numbers, defined by this recurrence relation:
๏ฎ
๏(๏ฎ)
0
1
1
1
2
2
3
3
4
5
5
8
6
13
7
21
8
34
9
55
10
89
11
144
12
233
Note that ๏(๏ฎ) di๏ฌers slightly from the canonical Fibonacci sequence,
which is defined by the same recurrence equation ๏ (๏ฎ) = ๏ (๏ฎ โ 1) +
๏ (๏ฎ โ 2) but the di๏ฌerent initial conditions, namely, ๏ (0) = 0 and ๏ (1) =
1๏บ Obviously, ๏(๏ฎ) = ๏ (๏ฎ + 1) for ๏ฎ โฅ 0๏บ
Note: The problem was included by Leonardo of Pisa (aka Fibonacci)
in his 1202 book Liber Abaci, in which he advocated usage of the HinduArabic numerals.
3. Let ๏ (๏ฎ) be the number of di๏ฌerent 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,
๏ (๏ฎ) = ๏ (๏ฎ โ 1) + ๏ (๏ฎ โ 2) for ๏ฎ โฅ 3๏ป
๏ (1) = 1๏ป ๏ (2) = 2๏บ
Solving this recurrence either โfrom scratchโ or better yet noticing that
the solution runs one step ahead of the canonical Fibonacci sequence ๏ (๏ฎ),
we obtain ๏ (๏ฎ) = ๏ (๏ฎ + 1) for ๏ฎ โฅ 1๏บ
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
that the Fibonacci numbers form the following pattern
even, odd, odd, even, odd, odd, …
Hence the number of even numbers among the first ๏ฎ Fibonacci numbers
can be obtained by the formula d๏ฎ๏ฝ3e๏บ
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๏บ
๏ฎ
The verification of ๏ฬ works out for the same reason. Since the equation
๏ (๏ฎ) โ ๏ (๏ฎ โ 1) โ ๏ (๏ฎ โ 2) = 0 is homogeneous and linear, any linear
๏ฎ
combination of its solutions ๏๏ฎ and ๏ฬ , i.e., any sequence of the form
๏ฎ
๏ฎ๏๏ฎ + ๏ฏ ๏ฬ will also be a solution to ๏ (๏ฎ) โ ๏ (๏ฎ โ 1) โ ๏ (๏ฎ โ 2) = 0๏บ In
๏ฎ
particular, it will be the case for the Fibonacci sequence โ15 ๏๏ฎ โ โ15 ๏ฬ ๏บ
Both initial conditions are checked out in a quite straightforward manner
๏ฎ
(but, of course, not individually for ๏๏ฎ and ๏ฬ )๏บ
6. a. The question is to find the smallest value of ๏ฎ such that ๏ (๏ฎ) ๏พ 231 โ 1๏บ
Using the formula ๏ (๏ฎ) = โ15 ๏๏ฎ rounded to the nearest integer, we get
(approximately) the following inequality:
โ
1
โ ๏๏ฎ ๏พ 231 โ 1 or ๏๏ฎ ๏พ 5(231 โ 1)๏บ
5
After taking natural logarithms of both hand sides, we obtain
โ
ln( 5(231 โ 1))
๏ฎ๏พ
โ 46๏บ3๏บ
ln ๏
Thus, the answer is ๏ฎ = 47๏บ
b. Similarly, we have to find the smallest value of ๏ฎ such that ๏ (๏ฎ) ๏พ
263 โ 1. Thus,
โ
1
โ ๏๏ฎ ๏พ 263 โ 1๏ป or ๏๏ฎ ๏พ 5(263 โ 1)
5
or, after taking natural logarithms of both hand sides,
โ
ln( 5(263 โ 1))
โ 92๏บ4๏บ
๏ฎ๏พ
ln ๏
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
the recurrence for ๏ (๏ฎ). The initial conditions will be:
๏(0) = 0๏ป ๏(1) = 1 and ๏(0) = 1๏ป ๏(1) = 0
for ๏(๏ฎ) and ๏(๏ฎ)๏ป respectively. Therefore, since both the recurrence
equation and the initial conditions for ๏(๏ฎ) and ๏ (๏ฎ) are the same, ๏(๏ฎ) =
51
๏ (๏ฎ)๏บ As to the assertion that ๏(๏ฎ) = ๏ (๏ฎ โ 1)๏ป it is easy to see that it
should be the case since the sequence ๏(๏ฎ) looks as follows:
1๏ป 0, 1, 1, 2, 3, 5, 8, 13, 21, …,
i.e., it is the same as the Fibonacci numbers shifted one position to the
right. This can be formally proved by checking that the sequence ๏ (๏ฎโ1)
(in which ๏ (โ1) is defined as 1) satisfies the recurrence relation
๏(๏ฎ) = ๏(๏ฎ โ 1) + ๏(๏ฎ โ 2) for ๏ฎ ๏พ 1 and ๏(0) = 1๏ป ๏(1) = 0๏บ
It can also be proved either by mathematical induction or by deriving an
explicit formula for ๏(๏ฎ) and showing that this formula is the same as the
value of the explicit formula for ๏ (๏ฎ) with ๏ฎ replaced by ๏ฎ โ 1๏บ
8. Algorithm Fib2( ๏ฎ)
//Computes the ๏ฎ-th Fibonacci number using just two variables
//Input: A nonnegative integer ๏ฎ
//Output: The ๏ฎ-th Fibonacci number
๏ต โ 0; ๏ถ โ 1
for ๏ฉ โ 2 to ๏ฎ do
๏ถ โ๏ถ+๏ต
๏ตโ๏ถโ๏ต
if ๏ฎ = 0 return 0
else return ๏ถ
9. (i) The validity of the equality for ๏ฎ = 1 follows immediately from the
definition of the Fibonacci sequence.
(ii) Assume that
โ
ยธ โ
ยธ๏ฎ
๏ (๏ฎ โ 1)
๏ (๏ฎ)
0 1
=
for a positive integer ๏ฎ๏บ
๏ (๏ฎ)
๏ (๏ฎ + 1)
1 1
We need to show that then
โ
ยธ โ
ยธ๏ฎ+1
๏ (๏ฎ)
๏ (๏ฎ + 1)
0 1
=
๏บ
๏ (๏ฎ + 1) ๏ (๏ฎ + 2)
1 1
Indeed,
โ
0 1
1 1
ยธ๏ฎ+1
=
=
โ
โ
0 1
1 1
0 1
1 1
ยธโ
ยธโ
0 1
1 1
ยธ๏ฎ
๏ (๏ฎ โ 1)
๏ (๏ฎ)
๏ (๏ฎ)
๏ (๏ฎ+1)
52
ยธ
=
โ
๏ (๏ฎ)
๏ (๏ฎ+1)
๏ (๏ฎ+1) ๏ (๏ฎ+2)
ยธ
.
10. The principal observation here is the fact that Euclidโs algorithm replaces
two consecutive Fibonacci numbers as its input by another pair of consecutive Fibonacci numbers, namely:
gcd(๏ (๏ฎ)๏ป ๏ (๏ฎ โ 1)) = gcd(๏ (๏ฎ โ 1)๏ป ๏ (๏ฎ โ 2)) for every ๏ฎ โฅ 4๏บ
Indeed, since ๏ (๏ฎ โ 2) ๏ผ ๏ (๏ฎ โ 1) for every ๏ฎ โฅ 4๏ป
๏ (๏ฎ) = ๏ (๏ฎ โ 1) + ๏ (๏ฎ โ 2) ๏ผ 2๏ (๏ฎ โ 1)๏บ
Therefore for every ๏ฎ โฅ 4๏ป the 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 ๏(๏ฎ):
๏(๏ฎ) = ๏(๏ฎ โ 1) + 1 for ๏ฎ โฅ 4๏ป
๏(3) = 1๏ป
whose initial condition ๏(3) = 1 is obtained by tracing the algorithm on
the input pair ๏ (3)๏ป ๏ (2)๏ป i.e., 2,1. The solution to this recurrence is:
๏(๏ฎ) = ๏ฎ โ 2 for every ๏ฎ โฅ 3๏บ
(One can also easily find directly that ๏(2) = 1 and ๏(1) = 0๏บ)
11. Given a rectangle with sides ๏ (๏ฎ) and ๏ (๏ฎ + 1)๏ป the problem can be
solved by the following recursive algorithm. If ๏ฎ = 1๏ป the problem is
already solved because the rectangle is a 1 ร 1 square. If ๏ฎ ๏พ 1๏ป dissect
the rectangle into the ๏ (๏ฎ) ร ๏ (๏ฎ) square and the rectangle with sides
๏ (๏ฎโ1) and ๏ (๏ฎ) and then dissect the latter by the same algorithm. The
algorithm is illustrated below for the 8 ร 13 square.
1ร1 1ร1
2 ร2
3ร3
8ร8
5ร5
53
Since the algorithm dissects the rectangle with sides ๏ (๏ฎ) and ๏ (๏ฎ + 1)
into ๏ฎ squaresโwhich can be formally obtained by solving the recurrence
for the number of squares ๏(๏ฎ) = ๏(๏ฎโ1)+1๏ป ๏(1) = 1โits time e๏ฌciency
falls into the ฮ(๏ฎ) class.
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 number of key comparisons.
Algorithm SortAnalysis(๏[0๏บ๏บ๏ฎ โ 1])
//Input: An array ๏[0๏บ๏บ๏ฎ โ 1] of ๏ฎ orderable elements
//Output: The total number of key comparisons made
๏ฃ๏ฏ๏ต๏ฎ๏ด โ 0
for ๏ฉ โ 1 to ๏ฎ โ 1 do
๏ถ โ ๏[๏ฉ]
๏ช โ๏ฉโ1
while ๏ช โฅ 0 and ๏[๏ช] ๏พ ๏ถ do
๏ฃ๏ฏ๏ต๏ฎ๏ด โ ๏ฃ๏ฏ๏ต๏ฎ๏ด + 1
๏[๏ช + 1] โ ๏[๏ช]
๏ช โ๏ชโ1
๏[๏ช + 1] โ ๏ถ
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.
b. Analyze the data obtained to form a hypothesis about the algorithmโs
average-case e๏ฌciency.
c. Estimate the number of key comparisons one should expect for a randomly generated array of size 10,000 sorted by the same algorithm.
3. Repeat Problem 2 by measuring the programโs running time in milliseconds.
4. Hypothesize a likely e๏ฌciency class of an algorithm based on the following
empirical observations of its basic operationโs count:
size
1000
count 11,966
2000
24,303
3000
39,992
4000
53,010
5000
67,272
6000
78,692
7000
91,274
8000
9000
10000
113,063 129,799 140,538
5. What scale transformation will make a logarithmic scatterplot look like a
linear one?
6. How can we distinguish a scatterplot for an algorithm in ฮ(lg lg ๏ฎ) from
a scatterplot for an algorithm in ฮ(lg ๏ฎ)?
55
7. a. Find empirically the largest number of divisions made by Euclidโs algorithm for computing gcd(๏ญ๏ป ๏ฎ) for 1 โค ๏ฎ โค ๏ญ โค 100๏บ
b. For each positive integer ๏ซ๏ป find empirically the smallest pair of integers 1 โค ๏ฎ โค ๏ญ โค 100 for which Euclidโs algorithm needs to make ๏ซ
divisions in order to find gcd(๏ญ๏ป ๏ฎ).
8. The average-case e๏ฌciency 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,
๏๏ก๏ถ๏ง (5) =
1
(1 + 2 + 3 + 2 + 1) = 1๏บ8๏บ
5
Produce a scatterplot of ๏๏ก๏ถ๏ง (๏ฎ) and indicate a likely average-case e๏ฌciency class of the algorithm.
9. Run an experiment to ascertain the e๏ฌciency class of the sieve of Eratosthenes (see Section 1.1).
10. Run a timing experiment for the three algorithms for computing gcd(๏ญ๏ป ๏ฎ)
presented in Section 1.1.
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.
3. On a reasonably fast desktop, you may well get zero time, at least for
smaller sizes in your sample. Section 2.6 mentions a trick for overcoming
this di๏ฌculty.
4. Check how fast the count values grow with doubling the size.
5. A similar question was discussed in the section.
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.
8. Get the empirical data for random values of ๏ฎ in a range of between, say,
102 and 104 or 105 and plot the data obtained. (You may want to use
di๏ฌerent scales for the axes of your coordinate system.)
9. n/a
10. n/a
57
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
first clause of the conjunction fails, the count should be simply incremented
by one either right before the while statement or right after the while
statementโs end. If the second clause of the conjunction is not executed
after the first clause fails, we should add the line
if ๏ช โฅ 0 ๏ฃ๏ฏ๏ต๏ฎ๏ด โ ๏ฃ๏ฏ๏ต๏ฎ๏ด + 1
right after the while statementโs end.
2. a. One should expect numbers very close to ๏ฎ2 ๏ฝ4 (the approximate theoretical number of key comparisons made by insertion sort on random
arrays).
b. The closeness of the ratios ๏(๏ฎ)๏ฝ๏ฎ2 to a constant suggests the ฮ(๏ฎ2 )
average-case e๏ฌciency. The same conclusion can also be drawn by observing the four-fold increase in the number of key comparisons in response to
doubling the arrayโs size.
c. ๏(10๏ป 000) can be estimated either as 10๏ป 0002 ๏ฝ4 or as 4๏(5๏ป 000)๏บ
3. See the answers to Exercise 2. Note, however, that the timing data is
inherently much less accurate and volatile than the counting data.
4. The data exhibits a behavior indicative of an ๏ฎ lg ๏ฎ algorithm.
5. If ๏ (๏ฎ) โ ๏ฃ log ๏ฎ, then the transformation ๏ฎ = ๏ก๏ซ (๏ก ๏พ 1) will yield
๏ (๏ก๏ซ ) โ (๏ฃ log ๏ก)๏ซ๏บ
6. The function lg lg ๏ฎ grows much more slowly than the slow-growing function 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 ๏ญ = 89 and ๏ฎ = 55)
b. Two consecutive Fibonacci numbersโ๏ญ = ๏๏ซ+2 ๏ป ๏ฎ = ๏๏ซ+1 โare the
smallest pair of integers ๏ญ โฅ ๏ฎ ๏พ 0 that requires ๏ซ comparisons for every
๏ซ โฅ 2๏บ (This is a well-known theoretical fact established by G. Lamรฉ (e.g.,
[KnuII].) For ๏ซ = 1๏ป the answer is ๏๏ซ+1 and ๏๏ซ , which are both equal to
1.
58
8. The experiment should confirm the known theoretical result: the averagecase e๏ฌciency of Euclidโs algorithm is in ฮ(lg ๏ฎ)๏บ For a slightly di๏ฌerent
metric ๏ (๏ฎ) investigated by D. Knuth, ๏ (๏ฎ) โ 12๏ผln2 2 ln ๏ฎ โ 0๏บ843 ln ๏ฎ (see
[KnuII], Section 4.5.3).
9. n/a
10. n/a
59

## Document Preview (59 of 499 Pages)

You are viewing preview pages of the document. Purchase to get full access instantly.

-37%

### Solution Manual For Introduction To The Design And Analysis Of Algorithms, 3rd Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

24/7 Live Chat

Instant Download

100% Confidential

Store

##### Amelia Rodriguez

0 (0 Reviews)

## Best Selling

The World Of Customer Service, 3rd Edition Test Bank

$18.99 ~~$29.99~~Save:$11.00(37%)

Chemistry: Principles And Reactions, 7th Edition Test Bank

$18.99 ~~$29.99~~Save:$11.00(37%)

Test Bank for Hospitality Facilities Management and Design, 4th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

Test Bank for Strategies For Reading Assessment And Instruction: Helping Every Child Succeed, 6th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

Data Structures and Other Objects Using C++ 4th Edition Solution Manual

$18.99 ~~$29.99~~Save:$11.00(37%)

Solution Manual for Designing the User Interface: Strategies for Effective Human-Computer Interaction, 6th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)