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).