Autumn 2000
CSE 373: Exercise Set O2:
FOR REVIEW SESSION, NOT FOR CREDIT
to be discussed in class December 6
Union-Find and Graphs
- 1. Exercise 8.1b. For union-by-height (rank), use the algorithm
of Figure 8.13. Start with an array of size 17 with each element initialized
to zero. Show how the array changes at each step. What is the depth of
the final tree? What happens to the tree if we do a find(17) with path
compression?
(Note: Same exercise and figure for the C++ book, however array
subscripts are 0 through 16, while the C book has them 1 through 17.
Change subscript 0 to 17 to get a consistent answer.)
- 2. Exercise 9.1. (Same for the C++ book) Find the topological
ordering of the given graph (ignoring the given weights on the edges)
using the topological sort algorithm.
- 3. Exercise 9.5a. (Same for the C++ book) Use Dijkstra's algorithm
to find all shortest paths starting from node A in the graph of Figure 9.80.
- 4. Exercise 9.16. (9.15a in the C++ book) Use Kruskal's algorithm
to find the minimal spanning tree for the weighted graph of Figure 9.82.