## Old Announcements:

• 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 yS=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 yS, 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  yS 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.
• 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