UMBC CMSC441, Design & Analysis of Algorithms, Fall 2001, Section 0101

Comments on the Final Exam

• The average for the regular final exam was 62% with a standard deviation of 13.0. The distribution of the scores were:

  90-100	1
  80-89	1
  70-79	3
  60-69	8
  50-59	9
  <50	2

  
  

• Problem I: This question had little to do with red-black trees except for the fact that they are balanced binary trees. The vast majority of you said that the items less than some node x in a red-black tree are all in the left subtree of x. This is of course not true. The items less than x consist of all the nodes to the left of the path from the root to x. All three schemes in part 1 would give you the parity in O(log n) time. For part 2, however, you don't want to use the first scheme, because once an item x is inserted you would have to update the parity of all the items > x. The second and third schemes work equally well. I prefer the last scheme because it is clear that after inserting x, you only have to update the parity of the ancestors of x. Insertions and deletions can be handled in the usual way, you only had to note that when you do a rotation, the parity information must be updated. This can be figured out from the parity information stored at the children of the affected node.

• Problem II: The choice is whether to include a theorem in the crib sheets or not. In the subproblem, we have to "remember" the number of lines left in the current index card. If we choose to take the theorem and it doesn't fit on the current card, we move on to the next card. The parameters of the subproblem are 1) the theorems remaining to be considered (i thru n) 2) the number of index cards left and 3) the number of lines remaining in the current index card. This gives us n x k x r subproblems. We can make the best choice in constant time which gives an O(nkr) algorithm.

• Problem III: Many people did not do the arithmetic for part 1. However, you can continue to part 2, which involves repeated swapping of the theorem with highest p/l ratio to the front. You cannot swap the theorem with the highest p/l ratio with just the first theorem. (It's easy to make a counterexample.) Part III, is then a fairly ordinary argument for greedy algorithms.

• Problem IV: You were asked to find the longest path in a DAG. Many people said BFS. This doesn't give you the longest path. It might give you the longest shortest path from the root, but that is not the same as the longest path. Most people also neglected to use the fact that the graph is acyclic. You can do a topological sort of the graph in time O(V+E), then starting from the "end" compute for each node, the longest path starting at that node as follows. For each node u, consider each edge (u,v). The longest path starting at u is either the "current" longest path or 1 + the longest path starting at v. (Yes, this smells like dynamic programming.)

• Problem V: Many people were discouraged by irrational numbers, but you can find the max flow and augmenting paths in the usual way. The max flow was 1 + r + r^2 = 2. You know this is the max flow because there is a cut with this capacity. The augmenting path with capacity 1 is straightforward. To get the right augmenting path with capacity r^2, you first go "forward" along the edge with capacity r, back along the edge with capacity 1 (which is now pointing backward) and then forward along the edge with capacity r^2. This augmenting path has capacity r^2. (Many people wrote down augmenting paths with capacity less than the capacity of the bottleneck edge. This is not allowed.) Then the edge which used to have forward capacity r, now has forward capacity r - r^2 = r^3. This allows you to come up with the next augmenting path with capacity r^3, and then one with capacity r^4, ... Even if you did not get parts 1-3, you can still sum the infinite geometric series (formula was in the crib sheet) and arrive at the conclusion that the flow constructed from this sequence of augmenting paths has a value that converges to 2, which is also the max flow. To get a flow network where an infinite sequence of augmenting paths does not converge to the maximum flow, simply take this network and add a new path from s to t with capacity 1. Then the max flow is 3, and the same sequence of augmenting paths described above still converges to 2.