• This is a closed-book, no calculators exam.
• It is more important that you do some work on every problem than it is to do a few problems very well and do nothing on the others.
• Show your work.

Question 1. Assume that at some stage in the Quick-Find algorithm, the id array has the entries shown.

1.A List the members of each of the sets defined by the array.

1.B Give a sequence of inputs of integer pairs (p, q) that would lead to the array shown. There are many sequences that will lead to the array shown; you need to write down only one such sequence.

Question 2. Explain the difference in complexity between the union operation in the Quick-Find algorithm and in the Quick-Union algorithm. Hint: The information that can help to explain the difference includes, among others: the complexity, "big-Oh" of the union operation in the Quick-Find algorithm, the tree structure of the Quick-Union data, and the operations involved in constructing the union in the Quick-Union algorithm.

Question 3. The figure below is the adjacency-list representation of a graph.

3.A Draw the graph corresponding to the adjacency list. In your drawing place node 0 at the top, node 5 at the lower left and node 6 at the lower right.

3.B Draw the adjacency matrix (1's and 0's) corresponding to the adjacency list. (Use your exam book lines for the horizontal lines of the matrix and draw 9 vertical lines to divide them up.)

Question 4. An algorithm requires 3N steps to reduce the problem size to N-1. The recurrence relation that describes this is:
     C_N = C_N-1 + 3N (for N > 1 and C₁ = 3)

4.A Solve the recurrence relation by "telescoping" it. What is the complexity of the solution in terms of N ("Big Oh")?

4.B Optional Extra Credit: How does the complexity of the solution above compare with the complexity derived from: C_N = C_N-1 + N ?

Question 5. To speed up search, sorting N items first allows binary search, which is quite efficient. As new items are added, instead of searching again, the new items can be added to a small separate unsorted array of size M so that if search of the large array fails, a sequential search of the smaller array can be done. If a new item is added every time a search is made, compare the time to search the large array plus the unordered array versus the time it would take to re-sort the entire set of N+M items and then do binary search. Do this for values: N=2¹⁰=1024, M=2⁵=32.

For simplicity, ignore the increase in size when estimating the time to sort and search when items are added, just assume that N+M is N. That is, always assume N=1024 for that part of the estimates. Assume that all searches of the large array fail and all searches of the small array are successful (to make your estimates easier to do). Hint: Note that the sort and binary search times for the large array may have very different complexity so that one may be safely neglected.

Optional Extra Credit: If additions are much less frequent than searches so that they are done only once for every K searches, estimate the value of K for which the two methods, using the small extra array or resorting, become approximately equal in cost (for the N=1024, M=32 example).