CS 500: Algorithms Design and Analysis

The scores have been updated with the claims from Hw #4, Hw #5, and the Final:

http://otfried.org/courses/cs500/grades.html

If the scores do not match your records, please send me email until tomorrow (Thursday).

You can now find your scores for the final exam at:

http://otfried.org/courses/cs500/posting-final.html

The course scoring table is also updated:

http://otfried.org/courses/cs500/grades.html

Note that that "Total" score is not yet final, since Hw #5 is not yet graded (the TAs have exams, too).

You can see the problems of the final again here:

http://otfried.org/courses/cs500/final.pdf

The correct answers for Problem 1 were:

F F T T F F T T T F

Problem 3 was designed so that you did not need to run Ford-Fulkerson.  It's pretty easy to find the smallest cut by trying a little, and then you easily construct a flow with the same value (by saturating all cut edges and working backwards from there).  Once you have that, you know that the cut must be minimal.   Surprisingly many students did it the hard way.

Problem 4 was the biggest shock.  This was nearly the same as a proof we did on the blackboard in the class:

 Make a flow network by directing all edges from U to V and giving them capacity 1.

 Add edges from a source s to U of capacity 2.

 Add edges from V to a sink t of capacity 5.

 Let n = |U|.  We construct a flow of value 2n as follows:

 Edges from s to U have flow 2.

 Edges from U to V have flow 1/9.

 Edges from V to t have flow 5.

 (This is a legal flow because of the degree condition: In U, 2 units come in and 18 * 1/9 go out,

  in V 45 * 1/9 come in and 5 go out).

 Since there is a cut of value 2n (namely {s}, U + V + {t}), this flow is maximal.

 By the integrality theorem, there is also a flow of value 2n with integer value on each edge.  

 So edges from U to V have flow zero or one.  Let H be those edges that have flow one.

 H satisfies the conditions required (U must have two outgoing edges in H, V must have 5 incoming edges in H).

Nobody found this easy and elegant solution, and in fact there were only very few fully correct solutions (they either used Hall's theorem, or explicitly analyzed the min-cut).

Problem 5:

Some students thought that meat sauce contains no mushrooms, and mushroom sauce contains no meat, even though the problem description clearly said "Both (sauces) are made from three ingredients".   I didn't count this wrong if the rest was correct.

To model it correctly, you really needed separate variables X_ij, where i is the sauce (meat sauce, mushroom sauce), and j is the ingredient.

Some students wrote constraints where they multiplied some variables.  That's completely forbidden in a linear program!

If you must see your final exam again, please come to my office on Monday (Jun 22), between 10am and noon.

The CS500 score page has been updated with Hw4 scores and the final attendance scores:

http://otfried.org/courses/cs500/grades.html

(Attendance is the number of lectures attended on time, Participation points is the resulting score following the rules explained on the web page.)

If you have any attendance tickets left that you did not yet register on the attendance server, please do it soon.

The attendance server will be turned off on the day of the final exam.

Homework 5 has been posted on the course website.

Needless to say this is the last homework :-)

Enjoy!

The semester is approaching its end, in particular for CS500:  Since I will be on a business trip in the last week of the semester, there is no class on June 10 and June 12.

Our final exam will be on June 15, from 9:00 to 12:00, again in room 1501 of building E3-1 (공동강의실, the same place as the midterm exam).  Please come on time so we can start at 9am sharp.

Now that the spring festival is over it's high time for the next homework.

Homework 4 is now posted on the course website.

The deadline is June 2.

Enjoy!