Posted by: yuanzhan | September 24, 2010

Grades of HW1 and some explanations

HW1 has been graded and will be handed out in today’s lecture. The main statistics about the scores (out of a total of 85) are:

  • Mean: 47.3085106
  • Median: 52.5
  • Standard Deviation: 24.295239

If you have any question about the grading of hw1, please contact me (Alex).

And here are some common mistakes in the homeworks:

  1. Most of you got points deducted for not providing the “proof idea” section.  As was mentioned in  the homework policy document and the grading rubric for HW 1, this part was required. Since this is the first time, we deducted only half of the total for this part. Please provide your “proof idea” section in the later homeworks, otherwise you will lose the entire points for the proof idea part. The proof idea will help us understand your idea better and give you better grades. You do not necessarily need to provide a proof idea as long as the ones we give in the solution sheets. As long as you state your idea clearly, and it is correct and precise, you will get full credit for this part.
  2. Also for most of you, points were taken off with an explanation like “you should not use G-S algorithm to prove this” or “G-S can only generate some stable matchings” in HW1. This mistake happened when you try to prove a claim about every stable matching for a stable matching instance. One example in the homeworks is (Q1,b). The claim here is the “special” pair (m,w) belongs to every stable matching S for this instance. Some of you used the G-S algorithm to generate one stable matching for this instance, and according to the algorithm, (m,w) is in this stable matching. The reason why this can’t work is that we need to show (m,w) is in every stable matching of this problem. What you’ve shown is only one stable matching which is found by G-S has one such pair. Therefore it’s not sufficient to prove the claim. I guess there’s a misunderstanding between the relation of Stable Marriage Problem and G-S algorithm. Note that one if a problem and the other is an algorithm to solve it. G-S outputs only one of the possible solutions for the stable marriage instance. So if we want to prove some property of all stable matchings, you cannot assume that G-S algorithm will “solve” it. Furthermore, G-S algorithm can only generate/find one stable matching of the problem, but you can not assume G-S algorithm will find all stable matchings for you. Recall that Atri mentioned in class that the G-S algorithm always outputs the same stable matching no matter how the free woman who proposes in every iteration is chosen. (For a more detailed discussion on this part, please see the textbook.) Thus, a stable matching instance that has more than one stable matching (and we saw an example in class), the G-S algorithm will not be able to output all of the stable matchings.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s