Java Reference
In-Depth Information
IN SHORT
24.1
Show the result of the following sequence of instructions:
union
(1, 2),
union
(3, 4)
, union
(3, 5),
union
(1, 7),
union
(3, 6),
union
(8, 9),
union
(1, 8),
union
(3, 10),
union
(3, 11),
union
(3, 12),
union
(3, 13),
union
(14, 15),
union
(16, 0),
union
(14, 16),
union
(1, 3), and
union
(1, 14) when the
union
operations are performed
a.
Arbitrarily
b.
By height
c.
By size
For each of the trees in Exercise 24.1, perform a
find
operation with
path compression on the deepest node.
24.2
Find the minimum spanning tree for the graph shown in
Figure 24.24.
24.3
24.4
Show the operation of the NCA algorithm for the data given in
Figure 24.8.
IN THEORY
24.5
Prove that for the mazes generated by the algorithm in Section 24.2.1
the path from the starting to ending points is unique.
24.6
Design an algorithm that generates a maze that contains no path from
start to finish but has the property that the removal of a
prespecified
wall creates a unique path.
24.7
Prove that Kruskal's algorithm is correct. In your proof do you
assume that the edge costs are nonnegative?
24.8
Show that, if a
union
operation is performed by height, the depth of
any tree is logarithmic.
figure 24.24
A graph
G
for
Exercise 24.3
2
V
0
V
1
10
1
3
7
8
5
V
2
V
3
V
4
9
10
11
6
12
V
5
V
6
Search WWH ::
Custom Search