CS410, Summer 1998
Quiz #9
July 24

Consult no sources.				Name:

1. In the tree implementation of union-find, what is the path
compression heuristic?

2. What does it mean for a sorting method to be stable?

3. What is the worst-case running time for insertion sort and on what
kind of input does it occur?

4. What is the best-case running time for insertion sort and on what
kind of input does it occur?

ANSWERS
=======

1. After you follow the path to the root, go through the path a second
time re-assigning each node on the path's parent pointer directly to
the root.

2. Ties are resolved according the original order of the objects.

3. O(n^2).  When the elements are originally in reverse-sorted order.

4. O(n).  When the elements are in sorted order.

2.5 points each.