10. Mental arithmetic A10×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])
2
3
3
10
10
9
9
11
12
11. Consider the following version of an important algorithm that we will
study later in the book.
Algorithm GE([0..−10])
12. von Neumann’s neighborhood How many one-by-one squares are gener-
ated 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
21
2 are illustrated below.
22
Hints to Exercises 2.3
1. Use the common summation formulas and rules listed in Appendix A. You
2. Find a sum among those in Appendix A that looks similar to the sum in
3. Just follow the formulas in question.
4. a. Tracing the algorithm to get its output for a few small values of (e.g.,
=12and 3) should help if you need it.
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.,
=12and 3) should help if you need it.
b. We faced the same question for the examples discussed in the sec-
tion. One of them is particularly pertinent here.
6. a. Elements [ ]and [ ]are symmetric with respect to the main
diagonal of the matrix.
7. Computing a sum of numbers can be done with −1additions. How
many does the algorithm make in computing each element of the product
matrix?
9. For the general step of the proof by induction, use the formula
X
=1
=
−1
X
=1
+
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
24
Solutions to Exercises 2.3
1. a. 1+3+5+7++999 =
500
P
(2–1) =
500
P
2–
500
P
1=2
500∗501
2–500 = 250000
b. 2+4+8+16+ +1024 =
10
P
=1
2=
10
P
=0
2−1=(2
11 −1) −1=2046
(Or by using the formula for the sum of the geometric series with =2
=2,and=9:+1 −1
−1=2
210 −1
2−1=2046)
4
h. P
=1 1(+1)=P
=1(1
−1
+1 )
=(
1
1−1
2)+(1
2−1
3)+ +( 1
−1−1
)+(1
−1
+1 )=1−1
+1 =
+1
(This is a special case of the so-called telescoping series–see Appendix
A–P
=(−−1)=−−1.)
2. a.
−1
P
=0
(2+1)
2=
−1
P
=0
(4+22+1)=
−1
P
=0
4+2
−1
P
=0
2+
−1
P
=0
1
25
c.
P
=1
(+1)2
−1=
P
=1
2−1+
P
=1
2−1=1
2
P
=1
2+
−1
P
=0
2
3. For the first formula: ()=2()= ()+()=[(−1) +
(−1)] + (+1)=3−1
4. a. Computes ()=
P
=1
2
b. Multiplication (or, if multiplication and addition are assumed to take
the same amount of time, either of the two).
5. a. Computes the range, i.e., the difference between the array’s largest and
smallest elements.
b. An element comparison.
−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.
−2
−1
−2
7. Replace the body of the loop by the following fragment:
[ ]←[ 0] ∗[0]
8. Let ()be the total number of times all the doors are toggled. The
problem statement implies that
()=
X
=1
bc
Appendix A),
()≤
X
=1
=(1+
X
=2
1)≤(1+Z
1
1
)=(1+ln )∈Θ(log )
and
()
X
=1
(−1) =
X
=1
1−
X
=1
1≥Z+1
1
1
−=ln(+1)−∈Θ(log )
9. Here is a proof by mathematical induction that
P
=1
=(+1)
2for every
positive integer
The young Gauss computed the sum
1+2+···+ 99 + 100
28
the class busy.) The Gauss idea can be easily generalized to an arbitrary
by adding
2
10. The object here is to compute (in one’s head) the sum of the numbers in
the table below:
2
3
3
3
10
10
10
9
9
9
11
11
12
The first method is based on the observation that the sum of any two num-
bers 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
11. a. The number of multiplications ()and the number of divisions ()
made by the algorithm are given by the same sum:
b. The inefficiency 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
12. The answer can be obtained by a straightforward evaluation of the sum
30
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≤≤9The next 90 numbers from 10 to 99 inclusive are
two-digits. Hence
31
Exercises 2.4
1. Solve the following recurrence relations.
a. ()=(−1) + 5 for 1(1) = 0
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: ()=1
3+2
3+···+3
4. Consider the following recursive algorithm.
Algorithm ()
//Input: A positive integer
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.)
6. BRestricted Tower of Hanoi Consider the version of the Tower of Hanoi
puzzle in which diskshavetobemovedfrompegAtopegCusingpeg
7. Ba. Prove that the exact number of additions made by the recursive
algorithm BinRec( )for an arbitrary positive integer is blog2c
8. a. Design a recursive algorithm for computing 2for any nonnegative
integer that is based on the formula: 2=2
−1+2
−1
9. Consider the following recursive algorithm.
Algorithm Riddle([0 −1])
//Input: An array [0 −1] of real numbers
a. What does this algorithm compute?
10. Consider the following algorithm to check whether a graph defined by its
adjacency matrix is complete.
Algorithm GraphComplete([0 −10 −1])
11. The determinant of an ×matrix
=
⎡
⎢
⎢
⎢
⎣
00 0−1
10 1−1
.
.
.
−10 −1−1
⎤
⎥
⎥
⎥
⎦
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, re-
gardless of whether one or two hamburgers are fried at the same time.
Consider the following recursive algorithm for executing this task. If
14. BCelebrity 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
Hints to Exercises 2.4
1. Each of these recurrences can be solved by the method of backward sub-
stitutions.
2. The recurrence relation in question is almost identical to the recurrence
3. a. The question is similar to that about the efficiency of the recursive
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
5. a. Use the formula for the number of disk moves derived in the section.
6. The required algorithm and the method of its analysis are similar to those
7. a. Consider separately the cases of even and odd values of and show that
for both of them blog2csatisfies the recurrence relation and its initial
condition.
8. a. Use the formula 2=2
−1+2
−1without simplifying it; do not forget
to provide a condition for stopping your recursive calls.
36
9. a. Tracing the algorithm for =1and =2should 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
11. a. Use the definition’s formula to get the recurrence relation for the num-
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
37
Solutions to Exercises 2.4
1. a. ()=(−1) + 5 for 1(1) = 0
b. ()=3(−1) for 1(1) = 4
Note: The solution can also be obtained by using the formula for the
term of the geometric progression:
()=(1)−1=4·3−1
38
e. ()=(3) + 1 for 1(1) = 1 (solve for =3
)
(3)=(3−1)+1
=[(3−2)+1]+1=(3−2)+2
=[(3−3)+1]+2=(3−3)+3
=
=(3−)+
=
=(3−)+=(1) + =1+log
3
3. a. Let ()be the number of multiplications made by the algorithm.
We have the following recurrence relation for it:
39
We can solve it by backward substitutions:
b. Here is a pseudocode for the nonrecursive option:
Algorithm NonrecS()
The number of multiplications made by this algorithm will be
4. a. ()=(−1) + 2−1for 1(1) = 1
Computing the first few terms of the sequence yields the following:
(2) = (1) + 2 ·2−1=1+2·2−1=4;
40