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