Posted by: jiunjiewang | October 2, 2012

The most common mistakes on this homework are listed as follows:

For Q2:
Some students give an algorithm as follows:

1. Initially, all students and hospitals are free.
And, the number of available candidates for each hospital h_i is p_i.

2. if the student s is not assigned to another hospital then:
s tentatively accepts the offer, and become assigned to h.
if the students is already assigned to another hospital , h’, then:
if  s prefers h to h’, then s accepts, and becomes tentatively assigned to h.
if  s prefers h’ to h, then s declines, and remains assigned to h’.

3. Repeat Step 2 until all of the slots are filled.

In the above algorithm, it’s NOT CLEAR to record the available candidates
for each hospital h_i. I mean that we should add a set of variables {c_1, c_2, …, c_m} into the above algorithm. Each c_i represents the number of available candidates for h_i. Initially, c_i=p_i for each i. As s prefers h_i to h_j and s accepts h_i, c_i should be decreased by one. And, c_j should be increased by one.

If you have the above mistake in your solution, you will loss 3~5 points.

For Q3:

Most students argue that  “2^{n^1.00001} grows slower than O( n^n)“.

The reason is as follows:

(1): 2^n is approximately equal to 2^{n^1.00001}.

(2): both functions 2^n and n^n are exponential function.
And 2^n is a slower growing than n^n.
So, 2^{n^1.00001} = O(n^n).

In the above argument,  2^n is NOT approximately equal to 2^{n^1.0001}
as n approaches infinity.
So, we can NOT assume  (1): 2^n is approximately equal to 2^{n^1.00001}.

If you prove by this way, you will loss 2~4 points.

For Q4,
1. Most student do not provide reduction. Or simply saying it is similar to SMP and no more.
2.Don’t know to prove stability. Some miss this part or give an example to be a “proof”.