Solutions to Exercises 5.3
1. Algorithm Levels ()
//Computes recursively the number of levels in a binary tree
2. The algorithm is incorrect because it returns 0 for any binary tree; in
particular, it returns 0 instead of 1 for the one-node binary tree. Here is
a corrected version:
3. Starting at the root, traverse the binary tree by breadth-first search to find
the level of each node. The largest of these numbers is, by the definition,
the height of the tree.
4. Here is a proof of equality (5.2) by strong induction on the number of
internal nodes ≥0. Thebasisstepistruebecausefor=0we have
the empty tree whose extended tree has 1 external node by definition. For
the inductive step, let us assume that
which completes the proof.
5. a. Preorder: abdecf
6. Here is pseudocode of the preorder traversal:
Algorithm Preorder()
//Implements the preorder traversal of a binary tree
//Input: Binary tree (with labeled vertices)
7. The inorder traversal yields a sorted list of keys of a binary search tree.
In order to prove it, we need to show that if 1
2are two keys in a
binary search tree then the inorder traversal visits the node containing 1
8. a. The root’s label is listed last in the postorder tree: hence, it is 2. The
labels preceding 2 in the order list–9,3,1,0,4–form the inorder traversal
list of the left subtree; the corresponding postorder list for the left subtree
traversal is given by the first four labels of the postorder list: 9,1,4,0,3.
21
Similarly, for the right subtree, the inorder and postorder lists are, respec-
tively, 7,6,8,5 and 6,7,5,8. Applying the same logic recursively to each of
the subtrees yields the following binary tree:
2
b. There is no such example for =2For =3lists 0,1,2 (inorder)
and 2,0,1 (postorder) provide one.
c. The problem can be solved by a recursive algorithm based on the
following observation: There exists a binary tree with inorder traversal
Algorithm Tree (0
1 −1
0
1 −1)
//Construct recursively the binary tree based on the inorder and postorder
traversal lists
9. We can prove equality =+2,whereand are, respectively,.
the external and internal path lengths in an extended binary tree with
internal nodes by induction on The basis case, for =0, holds because
22
both and are equal to 0 in the extended tree of the empty binary tree.
For the general case of induction, we assume that
=+2
=+2
where and are external and internal paths, respectively, in the right
subtree which has internal and external nodes, respectively.
Since the length of the simple path from the root of ()to a node in
()is one less than the length of the simple path from the root of
to that node, we have
10. n/a
11. We can represent operations of any algorithm solving the problem by a
full binary tree in which parental nodes represent breakable pieces and
23
at a time, any break increases the number of pieces by 1. Hence, −1
argument can be made more formally by mathematical induction.)
24
Exercises 5.4
1. What are the smallest and largest numbers of digits the product of two
decimal -digit integers can have?
4. a. Why did we not include multiplications by 10in the multiplication
count ()of the large-integer multiplication algorithm?
b. In addition to assuming that is a power of 2, we made, for the
sake of simplicity, another, more subtle, assumption in setting up a recur-
rence relation for ()which is not always true (it does not change the
final answer, however.) What is this assumption?
7. Apply Strassen’s algorithm to compute
⎡
⎢
1021
⎤
⎥
⎢
0101
⎤
⎥
8. Solve the recurrence for the number of additions required by Strassen’s
algorithm. (Assume that is a power of 2.)
9. V. Pan [Pan78] has discovered a divide-and-conquer matrix multiplication
10. Practical implementations of Strassen’s algorithm usually switch to the
brute-force method after matrix sizes become smaller than some “crossover
Hints to Exercises 5.4
1. You might want to answer the question for =2first and then generalize
it.
4. a. How do we multiply by powers of 10?
b. Try to repeat the argument for, say, 98 ∗76
6. Check the formulas by simple algebraic manipulations.
7. Trace Strassen’s algorithm on the input given. (It takes some work, but
itwouldhavebeenmuchmoreofitifyouwereaskedtostoptherecursion
Solutions to Exercises 5.4
1. The smallest decimal -digit positive integer is 100
|{z}
,i. e.,10
−1The
with 2digits, respectively, and 102−1102−2·10+1102−1).
2. For 2101 ∗1130:
2=21∗11
0=01∗30
1= (21 + 01) ∗(11 + 30) −(2+0)=22∗41 −21 ∗11 −01 ∗30
For 21 ∗11:
For 01 ∗30:
2=0∗3=0
0=1∗0=0
1=(0+1)∗(3 + 0) −(0 + 0) = 1 ∗3−0=3
So, 01 ∗30 = 0 ·102+3·101+0=30
For 22 ∗41:
Hence
27
3. a. Taking the base-logarithms of both hand sides of the equality log=
logyields loglog=log
log Since two numbers are equal if
and only if their logarithms to the same base are equal, the equality in
question is proved.
5. Let and be two -digit integers such that the product of each pair of
their digits is a one-digit number. Then the result of the pen-and-pencil
algorithm will look as follows:
:−1 10
:−1 10
6. 1+4−5+7=
(00 +11)(00 +11)+11(10 −00)−(00 +01)11 +(01 −11)(10 +11)=
0000 +1100 +0011 +1111 +1110 −1100 −0011 −0111 +0110 −
1110 +0111 −1111
=0000 +0110
7. For the matrices given, Strassen’s algorithm yields the following:
=∙00 01
10 11 ¸=∙00 01
10 11 ¸∙00 01
10 11 ¸
Therefore,
1=(00 +11)(00 +11)=∙40
62
¸∙12
71
¸=∙48
20 14 ¸
2=(10 +11)00 =∙31
71
¸∙01
21
¸=∙24
28
¸
29
Accordingly,
00 =1+4−5+7
=∙48
20 14 ¸+∙6−3
30
¸−∙83
10 5 ¸+∙32
−9−4¸=∙54
45
¸
That is,
=⎡
⎢
⎢
⎣
5473
4519
8137
5877
⎤
⎥
⎥
⎦
8. For =2
the recurrence ()=7(2)+18(2)2for 1(1) = 0
becomes
(2)=7(2−1)+9
24for 1(1) = 0
Solving it by backward substitutions yields the following:
30
Returningbacktothevariable=2
we obtain
9. The recurrence for the number of multiplications in Pan’s algorithm is
10. n/a
31
Exercises 5.5
1. a. For the one-dimensional version of the closest-pair problem, i.e., for the
problem of finding two closest numbers among a given set of real num-
bers, design an algorithm that is directly based on the divide-and-conquer
technique and determine its efficiency class.
3. Consider the version of the divide-and-conquer two-dimensional closest-
pair algorithm in which, instead of presorting input set ,wesimplysort
4. Implement the divide-and-conquer closest-pair algorithm, outlined in this
section, in the language of your choice.
5. Find on the Web a visualization of an algorithm for the closest-pair prob-
lem. What algorithm does this visualization represent?
6. The Voronoi polygon for a point of a set of points in the plane is
is generalized to the general case?
7. Explain how one can find point max in the quickhull algorithm analyti-
cally.
8. What is the best-case efficiency of quickhull?
32
11. Creating decagons There are 1000 points in the plane, no three of them
on the same line. Devise an algorithm to construct 100 decagons with
12. Shortest path around There is a fenced area in the two-dimensional Euclid-
ean plane in the shape of a convex polygon with vertices at points 1(1
1)
33
Hints to Exercises 5.5
1. a. How many points need to be considered in the combining-solutions
stage of the algorithm?
4. n/a
5. n/a
6. The answer to part (a) comes directly from a textbook on plane geometry.
10. n/a
11. Apply an idea used in this section to construct a decagon with its vertices
Solutions to Exercises 5.5
1. a. Assuming that the points are sorted in increasing order, we can find the
closest pair (or, for simplicity, just the distance between two closest points)
by comparing three distances: the distance between the two closest points
in the first half of the sorted list, the distance between the two closest
points in its second half, and the distance between the rightmost point in
the first half and the leftmost point in the second half. Therefore, after
sorting the numbers of a given array [0 −1] in increasing order, we
For =2
the recurrence for the running time ()of this algorithm is
()=2(2) +
Its solution, according to the Master Theorem, is in Θ(log22)=Θ()If
sorting of the input’s numbers is done with a Θ(log )algorithm such
as mergesort, the overall running time will be in Θ(log )+Θ()=
Θ(log )
2. Since both sides of each of the eight rectangles is no larger than 2the
distance between any two of its points cannot exceed the length of its
35
to and therefore all of them cannot contian more than eight such points.
x = m
3. ()=2(2) + 2
2log2
2for 2(and =2
)(2) = 1
Thus, (2)=2(2−1)+2
(−1)Solving it by backward substi-
tutions yields the following:
(2)=2(2−1)+2
(−1)
=2[2(2−2)+2
−1(−2)] + 2(−1) = 22(2−2)+2
(−2) + 2(−1)
4. n/a
6. a. The Voronoi diagram of three points not on the same line is formed by
the perpendicular bisectors of the sides of the triangle with vertices at 1
2and 3:
2
P
3
P
7. Since all the points in question serve as the third vertex for triangles with
the same base 1the farthest point is the one that maximizes the area
of such a triangle. The area of a triangle, in turn, can be computed as
one half of the magnitude of the determinant
8. If all points lie on the same line, both 1and 2will be empty and the
convex hull (a line segment) will be found in linear time, assuming that
9. Among many possible answers, one can take two endpoints of the hori-
zontal diameter of some circumference as points 1and and obtain the
10. n/a
11. We assume without loss of generality that the points are numbered left
to right from 1 to 1000with ties, if any, resolved by numbering a lower
of the two points first. Consider the first ten points 1 10 and draw
the straight line connecting 1and 10 There are two cases: either all
the other eight points 2 9lie on the same side of this line (see the
12. Find the upper and lower hulls of the set { 1 }(e.g., by quick-
hull), compute their lengths (by summing up the lengths of the line seg-
ments making up the polygonal chains), and return the smaller of the
two.
38