CPS 100, Spring 2004, Week 1 Warm-up

Read pages 7-18 (up to path compression) in Algorithms in C++ by Robert Sedgewick.

Questions about Reading

    Consider the following implementations of Quick-find (UnionFind) and Quick-union (QuickUnionFind) in fastfind.cpp.

  1. Show the output produced by the program.Do not compile and run the program. Simulate it by hand.
  2. For random data, which algorithm would you expect to be faster, quick-union or quick-find? Explain why? Describe some tradeoffs between quick-union and quick-find.
  3. Problem 1.10 and 1.11 from Algorithms in C++.
Jeff Forbes
Last modified: Sat Jan 10 22:21:54 EST 2004