COMMENTS ON PROBLEM SET 1
by Mohammad Mahdian

I was very lenient in marking and gave some partial marks to any student
who tried in some good direction to solve a problem. Also, I gave full
mark to students who have solved the problem, but have small mistakes.

In problem 2 (b), some students have written a counter-example that
consists of two vertices and two parallel edges between them. I gave
full-mark (2) to them, because it is not written explicitly (neither in
the problem set, nor in the lecture notes) that graphs cannot have
multiple edges, and I thought that some student might have seen other
definitions of graphs, allowing multiple edges, in some other course.

In problem 3, some students have found an interesting solution (which in
fact was the only completely correct solution): It is clear that in the
optimal solution, there are at most p-1 coins of value p^i, for each i.
Therefore, if p^i is the largest coing that fits, the optimal solution
must contain p^i, since (p-1)*p^{i-1}+...+(p-1)*p+(p-1)  is less than p^i. 

I gave 4 marks to students who tried in the right direction, but couldn't
prove it rigorously that if p^i is the largest coin that fits, then there
is a subset of the optimal solution with sum equal to p^i.

Problem 4 was the easiest one. Most of the students solved it.

Problem 5 was the most difficult problem. Almost all of the students have
written the Floyd's algorithm as the solution to this problem. I gave 2
marks to those kind of solution.