Homework 3 has been graded. The average was 16. Some comments (the detailed solutions are on the webpage, with the solution to problem 1 to be posted tomorrow).
1. Most of you got this one right. The reason why the binary search solution was not strongly poly-time was that the number of steps depends on the size of the numbers involved.
2. For this one, a few solutions tried proving it from first principles. All these statements can be proved in that way, but the easier way is to prove one version of the Farkas lemma (which you’ve already done in HW2) and then reduce these other versions to that one.
3. No surprises here, nothing to report.
4. Perhaps a majority of the solutions reduced it to standard matching and used Hall/Konig’s theorem to prove this statement. Perfectly kosher, even though I was hoping for the duality-based solution.
We give back the graded HWs 2 and 3 at the end of lecture tomorrow.
Leave a Reply