capacity
0123456
0 0 000000
8. For the problem of computing a binomial coefficient, we know in advance
which cells of the table need to be computed. Therefore unnecessary
9. n/a
21
Exercises 8.3
1. Finish the computations started in the section’s example of constructing
an optimal binary search tree.
4. Devise a way to compute the sums P
=which are used in the dynamic
programming algorithm for constructing an optimal binary search tree, in
constant time (per sum).
7. a. Show that the number of distinct binary search trees ()that can be
constructed for a set of orderable keys satisfies the recurrence relation
8. IDesign a Θ(2)algorithm for finding an optimal binary search tree.
9. BGeneralize the optimal binary search algorithm by taking into account
unsuccessful searches.
whose dimensions are 0×1
1×2 −1×, respectively. (As-
sume that all intermediate products of two matrices are computed by the
brute-force (definition-based) algorithm.
23
Hints to Exercises 8.3
1. Continue applying formula (8.8) as prescribed by the algorithm.
2. a. The algorithm’s time efficiency can be investigated by following the
standard plan of analyzing the time efficiency of a nonrecursive algorithm.
5. If the assertion were true, would we not have a simpler algorithm for
constructing an optimal binary search tree?
6. The structure of the tree should simply minimize the average depth of its
nodes. Do not forget to indicate a way to distribute the keys among the
nodes of the tree.
9. Assume that 1 are distinct keys ordered from the smallest to the
largest, 1 are the probabilities of searching for them, and 0
1
are probabilities of unsuccessful searches for keys in intervals (−∞
1)
(1
2) (∞)respectively; (1+··· +)+(0+···+)=1
Set up a recurrence relation similar to recurrence (8.8) for the expected
2×3and then choose some specific values for the dimensions to get a
required example.
b. You can get the answer by following the approach used for count-
25
Solutions to Exercises 8.3
1. The instance of the problem in question is defined by the data
key
probability 0.1 0.2 0.4 0.3
The table entries for the dynamic programming algorithm are computed
as follows:
[13] = min
=1:[10] + [23] + P3
=1 =0+08+07=15
=2:[11] + [33] + P3
=1 =01+04+07=12
=3:[12] + [43] + P3
=1 =04+0+07=11
=11
the main table
01234
100.10.41.11.7
the root table
01234
11233
the optimal tree
C
26
2. a. The number of times the innermost loop is executed is given by the
sum
−1
X
=1
−
X
=1
+
X
=
1=
−1
X
=1
−
X
=1
(+−+1)=
−1
X
=1
−
X
=1
(+1)
3. Call OptimalTree(1)below:
Algorithm OptimalTree( )
//Input: Indices and of the first and last keys of a sorted list of keys
4. Precompute =P
=1 for =12and set 0=0Then P
=
can be found as −−1for any 1≤≤≤
5. False. Here is a simple counterexample: (03)(03)(04)(The
numbers in the parentheses indicate the search probabilities.) The average
6. Thebinarysearchtreeinquestionshouldhaveamaximalnumberofnodes
on each of its levels except the last one. (For simplicity, we can put all
the nodes of the last level in their leftmost positions possible to make it
complete.) The keys of a given sorted list can be distributed among the
nodes of the binary tree by performing its in-order traversal.
7. a. Let ()be the number of distinct binary trees with nodes. If the
left subtree of a binary tree with nodes has nodes (0 ≤≤−1),
the right subtree must have −1−nodes. The number of such trees
is therefore ()(−1−)Hence,
28
8. The dynamic programming algorithm finds the root kmin of an optimal
binary search tree for keys by minimizing {[ −1]+[+1]}
for ≤≤ As pointed out at the end of Section 8.3 (see also [KnuIII],
p. 456, Exercise 27), [ −1] ≤kmin ≤[+1]This observation
By ”telescoping” the first sum, we can see that all its terms except the
two get cancelled to yield
P−
=1 ([+1+]−[ +−1]) =
=([21+]−[11+−1])
+([32+]−[22+−1])
Hence,
−1
X
=1
−
X
=1
[+1]
X
=[−1]
1=
−1
X
=1
([−+1]−[1]+−)
−1
X
=1
222
9. Let 1 be a sorted list of distinct keys, be a known probability
of searching for key for =12 and be a known probability of
searching (unsuccessfully) for a key between and +1 for =01
(with 0being a probability of searching for a key smaller than 1and
10. Algorithm MFOptimalBST ( )
//Returns the number of comparisons in a successful search in a BST
//Input: Indices indicating the range of keys in a sorted list of keys
//and an array [1]of search probabilities used as a global variable
11. a. Multiplying two matrices of dimensions ×and ×by the definition-
based algorithm requires multiplications. (There are elements
in the product, each requiring multiplications to be computed.) If the
b. Let ()be the number of different ways to compute a chain product
of matrices 1· ·Any parenthesization of the chain will lead to
multiplying, as the last operation, some product of the first matrices
(1· ·)and the last −matrices (+1 · ·)There are ()
ways to do the former, and there are (−)ways to do the latter.
31