for the number of binary trees mentioned in Section 8.3. Nor is it sur-
prising that their solutions are very similar, too: namely,
()=(−1) for ≥1
where ()is the number of binary trees with nodes. Let us prove
this assertion by mathematical induction. The basis checks immediately:
c. Let [ ]be the optimal (smallest) number of multiplications needed
for computing · ·If is an index of the last matrix in the first
factor of the last matrix product, then
[ ]= max
1≤≤−1{[ ]+[+1]+−1}for 1≤≤
[ ]=0
32
To find an optimal order to multiply the matrix chain, call OptimalMulti-
plicationOrder(1)below:
Algorithm OptimalOrder ( )
//Outputs an optimal order to multiply matrices
//Input: Indices and of the first and last matrices in and
Exercises 8.4
1. Apply Warshall’s algorithm to find the transitive closure of the digraph
defined by the following adjacency matrix:
2. a. Prove that the time efficiency of Warshall’s algorithm is cubic.
3. Explain how to implement Warshall’s algorithm without using extra mem-
ory for storing elements of the algorithm’s intermediate matrices.
4. Explain how to restructure the innermost loop of the algorithm Warshall
to make it run faster at least on some inputs.
7. Solve the all-pairs shortest path problem for the digraph with the following
weight matrix: ⎡
02∞18
⎤
8. Prove that the next matrix in sequence (8.8) of Floyd’s algorithm can be
written over its predecessor.
9. Give an example of a graph or a digraph with negative weights for which
34
11. Jack Straws In the game of Jack Straws, a number of plastic or wooden
“straws” are dumped on the table and players try to remove them one
by one without disturbing the other straws. Here, we are only concerned
35
Hints to Exercises 8.4
1. Apply the algorithm to the adjacency matrix given as it is done in the
section for another matrix.
2. a. The answer can be obtained either by considering how many values the
3. Show that we can simply overwrite elements of (−1) with elements of
()without any other changes in the algorithm.
4. What happens if (−1)[ ]=0?
7. See an example of applying the algorithm to another instance in the sec-
tion.
8. What elements of matrix (−1) does ()
, the element in the th row and
the th column of matrix ()depend on? Can these values be changed
by the overwriting?
36
Solutions to Exercises 8.4
1. Applying Warshall’s algorithm yields the following sequence of matrices
(in which newly updated elements are shown in bold):
(0) =⎡
⎢
⎢
⎣
0100
0010
0001
0000
⎤
⎥
⎥
⎦(1) =⎡
⎢
⎢
⎣
0100
0010
0001
0000
⎤
⎥
⎥
⎦
2. a. For a graph with vertices, the algorithm computes matrices ()
(=12 ),eachofwhichhas2elements. Hence, the total number
of elements to be computed is 3Since computing each element takes
constant time, the time efficiency of the algorithm is in Θ(3)
3. Thealgorithmcomputesthenewvaluetobeputintheth row and the
th column by the formula
()[ ]=(−1)[ ]or ((−1)[ ]and (−1)[ ])
4. If (−1)[ ]=0
()[ ]=(−1)[ ]or ((−1)[ ]and (−1)[ ]) = (−1)[ ]
and hence the innermost loop need not be executed. And, since (−1)[ ]
doesn’t depend on itscomparisonwith0canbedoneoutsidetheloop.
5. First, it is easy to check that
← or ( and )
is equivalent to
if ← or
Indeed, if =1(i.e., true),
6. a. With the book’s definition of the transitive closure (which considers
only nontrivial paths of a digraph), a digraph has a directed cycle if and
only if its transitive closure has a 1 on its main diagonal. The algorithm
that finds the transitive closure by applying Warshall’s algorithm and then
7. Applying Floyd’s algorithm to the given weight matrix generates the fol-
lowing sequence of matrices:
⎡
⎢
⎢
02∞18
6032∞
⎤
⎥
⎥
⎡
⎢
⎢
02∞18
603214
⎤
⎥
⎥
8. The formula
()
=min{(−1)
(−1)
+(−1)
}
9. As a simple counterexample, one can suggest the following digraph:
ab
– 2
1
Floyd’s algorithm will yield:
10. As pointed out in the hint to this problem, Floyd’s algorithm should be
enhanced by recording in an -by-matrix index of an intermediate
vertex causing an update of the distance matrix. This is implemented in
the pseudocode below:
Algorithm FloydEnhanced ([1 1])
For example, for the digraph in Fig. 8.7 whose vertices are numbered from
1to4,matrixwill be as follows:
=⎡
⎢
⎢
⎣
0303
0013
4000
0310
⎤
⎥
⎥
⎦
The list of intermediate vertices on the shortest path from vertex to
vertex can be then generated by the call to the following recursive algo-
rithm, provided [ ]∞:
Algorithm ShortestPath( [1 1])
//The algorithm prints out the list of intermediate vertices of
11. First, for each pair of the straws, determine whether the straws intersect.
(Although this can be done in log time by a sophisticated algorithm,
the quadratic brute-force algorithm would do because of the quadratic