CPSC 411: Comments on HW 3 Solutions

CPSC 411: Comments on HW 3 Solutions
October 15, 2008

Ex. 15.4-5: Worst-case time for quicksort is Theta(n^2), not O(n log n). But any sorting algorithm with running time O(n^2) will do.
Prob. 15-4: Dependencies among subproblems are that you need to have already solved the subproblems for the descendants of node i before considering node i. A total order that is consistent with these dependencies is to go by decreasing level (distance from the root) and left to right among nodes at the same level, as in the figure on p. 2. Running time is O(V) since each node is considered a constant number of times (self, as a child of its unique parent, and as a grandchild of its unique grandparent).
Prob. 15-5 (a). Solution I gave in class used "true" and "false". Note how in Yue's solution he uses 1 and 0, and then it is easy to compute whether there exists a predecessor node u of v with the given label, by using the MAX function. Dependencies among the subproblems are that you must have already computed A(i-1,*)'s before computing any A(i,*). A total order consistent with these dependencies is to go row by row, going down. The running time is O(kn^2) (not O(nk)), since computing the max requires considering all predecessors of v, and there might be as many as n of them.
Prob. 15-5 (b). In this case, the MAX is applied to arbitrary numbers (probabilities), not just 0's and 1's as in part (a). Same comment about the running time as for part (a).
Ex. 17.1-3: Use formula (A.5) in Appendix A to calculate the value of the sum, from i = 0 to floor(lg n), of 2^i.
Ex. 17.3-2: There is a small bug in the solution: the potential function is not defined for i = 0. However, just by explicitly setting Phi(0) = 0, the problem is fixed.
An alternative way of phrasing the potential function, which might be a little easier to understand and to manipulate, is this: Let s(i) be the smallest nonnegative integer such that 2^{s(i)} > i. (So s(0) = 0, s(1) = 1, s(2) = s(3) = 2, s(4) = s(5) = s(6) = s(7) = 3, etc.)
Define Phi(D_i) to be 2i - 2^{s(i)}. We have to show that Phi(D_i) >= Phi(D_0) for all i. Since Phi(0) = -1 and Phi(D_i) is nonnegative for all i > 0, we are OK. (It is not necessary that Phi(D_0) equal 0, it is just necessary that Phi(D_i) >= Phi(D_0).)
Note that Phi(D_i) - Phi(D_{i-1}) >= 2 - (2^{s(i)} - 2^{s(i-1)}).
Case 1: i = 2^k for some k. Then s(i) = k+1 and s(i-1) = k. So the amortized cost of the i-th operation is 2^k + 2 - (2^{k-1} - 2^k) = 2.
Case 2: i is not a power of 2. Then s(i) = s(i-1). so the amortized cost of the i-th operation is 1 + 2 - (2^{s(i)} - 2^{s(i)}) = 3.
Ex. 17.4-3. In case (a), there are 3 subcases, depending on whether (1) the table is at least half full before and after the deletion, (2) the table is less than half full before and after the deletion, or (3) the table is at least half full before and less than half full after the deletion. Because of the use of the absolute value in the potential function definition, you have to take into account the 3 different cases. The amortized cost for subcase (1) is -1, the amortized cost for subcase (2) is 3, and the amortized cost for subcase (3) is 3.
In case (b), the "before" and "after" expressions got reversed. The argument goes like this: 2*num_i - size_i = 0 since the table is exactly half full after the contraction (remember the diagram I drew in class). Also, 2*num_{i-1} - size_{i-} equals 2*num_{i-1} - 3*num_{i-1}, since the table was 1/3 full just before the contraction. If you plug in and do the algebra, you find that the amortized cost in this case is 0.
Ex. 21.2-2: The figure should consist of 16 nodes in one linked list. Both Find-Sets return x1.
Ex. 21.3-1: The end result should look like this: Node 16 is the root and has children 2, 4, 8, 9, 10, 12, 13, 14, 15. Node 4 has child 3. Node 8 has children 1, 5, 6 and 7. Node 12 has child 11.
Ex. 21.4-4: Lemma 21.4 says that each non-root node has a smaller rank than that of its parent. Ex. 21.4-2 says that the maximum rank is floor(log n). Thus the maximum time taken by any Find-Set is O(log n), since the maximum length of any path in a tree is O(log n). Since Unions take constant time (excluding any embedded Find-Sets) and Make-Sets take constant time, the total time for m operations is O(m log n).