- Question 2 in Problem set 6 depends on the generalized assignment 2-approximation that I did not finish in class on Friday. As a result, you only have to do one of the 3 problems on this problem set.
- Problem Set 4 has been clarified (on October 28th). Problem 4 a bit simplified and sequence alignment better explained), and a typo fixed in Problem 1.
- Here are some practice questions that may help you prepare for the midterms.
- Two hints for Problem 4 on this practice set:
- It is enough to permute rows or columns, no need to permute them both.
- The problem is an application of the matching problem.

- Here are the Solutions to Problem Set 2 with two minor typos fixed on 10/21.
- Here are the Solutions to Problem Set 3.
- Eva Tardos's office hours for the week of the midterm: Tuesday, October 22nd 2:30-3:30
- Typo fixed in Problem 1a (initial flow was set wrong) on Problem set 3.
- The in-class Midterm is Wednesday October 23rd, 2:30-4pm. Please let us know immediately if you have a conflict with this time.
- Notes on the project selection problem are available from Esha Mollette in 4119 Upson.
- The Boykov, Veksler, and Zabih paper using graphs cuts for stereo matching.
- Problem set 3 (due Oct 18th).
- Question 3(a) on PS3 is changed to require you to find the rounding (rather than just output "yes, the rounding exists").
- Clarification for Problem 2
on Problem set 2:
- In part 2b, after changing the costs by subtracting the y values, we only contract the 0 cost cycles.
- A better way to
state the cost-sharing process is this. Start by setting y
_{S}=0 for all sets S. Now in each iteration, consider all current super-nodes. Let S be the set of original nodes included in this super-node, find the minimum cost of an edge entering the super-node, say this minimum cost is c, then add c to the y_{S}, and subtract c from the cost of all edges entering the set S. If a set of nodes S occurs as a super-node in only one iteration, than this process is exactly the same as the way it is described in the problem set. However, if a set S is a super-node in multiple iterations, we do not want the later settings of the y_{S }values to overwrite the older ones. In the case of 2b, we do example the same, except that in each iteration uses one c value for all current super-nodes, namely the minimum cost of an edge in the current graph.

- Here are the solutions to Problem Set 1.
- No class on Wednesday, October 2nd. Please attend the CS Colloquium by Jim Gray at that time on "Can Databases Help Science?"
- Extra handouts on the preflow/push maximum flow algorithm can be picked up from Esha Mollette in 4119 Upson.
- Problem set 2 (due Oct 4th).
- Extra handouts on the minimum cost arborescence problem can be picked up from Esha Mollette in 4119 Upson.
- Problem set 1 (due Sept 20th).
- You should assume
throughout that
**m**is the number of edges,**n**is the number of nodes and**m > n**. - You may assume in all problems that all weights are different, though the problems can also be solved without this assumption.

- You should assume
throughout that
- In class we skipped a small part of a proof. Many of you sent me ideas, and proofs. THANKS! Here are two proofs that came out of this. (The second one was my original proof, I like the first one more.)
- The CS 482 book is now available in the campus store under the name of "CS681 course packet"
- Karger, Klein, and Tarjan MST Paper