Posted by: Jesse | September 23, 2011

## HW 1 Grades

Homework 1 has been graded and will be handed back in recitations and TA office hours.  The stats for homework 1 are:

• Mean: 73
• Median: 77
• Standard Deviation: 23

These numbers do not reflect students who received a 0.  Throughout the semester the 0’s will not be used when calculating these statistics.

There were a few common mistakes on this homework that we would like to go over.

• Many of you are not including an explicit “proof Idea” section.  This section needs to be on any problem with a proof.  If there is any confusion about this, refer to the grading rubric for the homework which will outline where your points will come from.  Also, whether you are proving that a statement is true, or proving that it is false, it is still a proof.
• On question 1, the most common mistake was proving the statements using the GS-algorithm instead of the stable matching problem in general.  This is an important distinction that can be subtle.  The GS-algorithm is only one way to solve the stable matching problem, there are others.  For example, you have seen the brute force algorithm.  There is no guarantee that each algorithm will output the same stable matchings.  There could be an algorithm that outputs a matching that can never be reached using the GS-algorithm.  Thus, when proving the statements in question 1, you must focus on the stable matching problem in general.  Notice that the solutions never mention a specific algorithm.
• For 1a specifically, to disprove the statement it must be shown that there is an instance such that for all stable matchings there is a pair that prefer each other the least.  Many of you showed that there was one stable matching by running the GS-algorithm.  For example, if you used n=2 there are a total of 2!=2 perfect matchings.  It is not enough to show that one of them fulfills the condition.  You must either show that they both do, or that the other one is unstable.
• Also, if you collaborated with someone, please write who you collaborated with on your paper.  There were several instances where someone listed a collaborator who did not list them back.

Here is a note from Jiun-Jie about problem 2:

There is a common problem in question 2.
Some students provide another algorithm different from the original solution.
I list their method as following:
***********************************************************************
while there is a student s who is not accepted yet.
let h be the highest rank of s such that h does not reject s.
(It implies schools {h1, h2, …, ht} have rejected s and schools {h1, h2, …, ht} have higher rank than h in s.)
If h has an open position,
(h, s) is a new assignment
Else  (h, s’) is an assignment such that
s’ is the least preferred students assigned to h
if h prefer s’ to s,
h rejects s and
s remains free.
else
the assignment (h, s) replace  (h, s’),
h rejects s’ and
s’ is now free.
end if
end if
end while
****************************************************************************************
This algorithm is correct but not efficient.
It takes O(m*n*k) where k is the maximum number of slots among all  hospitals.

-If there are any questions, send an email to all three of us.  Sending it to all of us will minimize the turn-around time for your question.