CPSC 320 2020W1: Assignment 1
1 Statement on Collaboration and Use of Resources
2 Gale-Shapley-ish Algorithm
In this problem, we will explore a dierent algorithm to solve the Stable Matching Problem. The algorithm is similar to the Gale-Shapley algorithm, so we will call it the GSish algorithm.
Intuitively, the algorithm initially assigns to each employer its top-ranked applicant. But this can result in an applicant being assigned to multiple employers. So, then, whenever the algorithm nds two employers who are assigned the same applicant, it lets the applicant pick whichever employer he/she prefers, and the losing employer immediately gets assigned its next choice in its preference list.
As in the worksheets, we will use E to denote the set of employers, A to denote the set of applicants, PE to denote the complete set of employer preferences, and PA to denote the complete set of applicant preferences. We will use the > symbol with subscripts to denote comparisons based on preferences. For example, a >e a′ says that employer e prefers applicant a to applicant a′. We will assume that there are n employers and n applicants, i.e., |E| = |A| = n. Here is the GSish algorithm:
1:
2:
3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17:
procedure GSish(E, A, PE, PA)
// Let M ⊆ E × A be the matching we are constructing.
Initialize M to be the set of all pairs (e, rst(e)) for all e ∈ E, where rst(e) denotes e’s top-ranked applicant.
while∃e,e′ ∈E,a∈Asuchthat(e̸=e′)∧((e,a)∈M)∧((e′,a)∈M)do if e >a e′ then
// a prefers e
Remove (e′ , a) from M .
Add (e′,a′) to M, where a′ is e′’s next choice after a.
If there is no next choice (a was e′’s last choice), then break out of the while loop.
else
// a prefers e′
Remove (e, a) from M .
Add (e,a′) to M, where a′ is e’s next choice after a.
If there is no next choice (a was e’s last choice), then break out of the while loop.
end if end while
return the matching M end procedure
In the following proofs, you may not assume the later parts of this question to be true in proving the earlier parts. However, you may assume the earlier parts of the problem to be true in your proofs for the later parts.
1. Prove that the number of iterations of the while loop is upper-bounded by n2. (Hint: On each iteration of the loop, we remove an employer-applicant pair from M. Could we ever remove this same pair again? Why or why not?)
1
Each iteration of the loop removes a pair (e′,a) or (e,a) from M. This same pair will never get added again back to M because the employer will move downward on its preference list. Hence, the same pair can never be removed twice. Since there are a total of n × n pairs of the form (e, a) with e ∈ E and a ∈ A, the loop can repeat at most n2 times.
2. Suppose that the sets E and A are represented simply as the set of integers from 1 to n. And suppose that PE and PA are supplied to the algorithm as arrays of linked lists. E.g., PE[4] is the head of a linked list of integers, which contains the numbers of all the applicants in the order that employer 4 likes them (best comes rst). This makes it very easy to implement the operation of nding the next choice for the losing employer (on lines 7 and 12) in O(1) time, as we can simply follow the link to the next applicant. However, it’s not clear how to do the comparison on line 4 in constant time. Explain how you could implement that comparison in constant time. (Hint: You can do up to O(n2) pre-processing before the while loop starts without messing up the asymptotic time complexity of the algorithm.)
The key is to pre-process the preference lists so that we can easily look up the rank of each em- ployer/applicant. For example, we can create two n × n arrays of integers, RE and RA. So, for instance, RE[1][2] = 3 means that employer 1 ranks applicant 2 as the 3rd best applicant on its list, and RA[4][5] = 6 meanas that applicant 4 ranks employer 5 as the 6th best employer on his/her list. n Actually, for this code, we need only the applicants’ rankings, so we can pre-compute RA in O(n2) time using code like:
fora∈Ado
Let e = PA[a], i.e., a’s top-ranked employer for i = 1,…,n do
Let RA[a][e] = i
Let e be the next employer on a’s list. end for
1: 2: 3: 4: 5: 6: 7:
the array n + 1 by n + 1.) That code is executed once, before the while loop.
Then, to implement the e >a e′ comparison on line 4 of the GSish algorithm, we can just compare
ranks: RA[a][e] < RA[a][e′].
3. Prove that each employer is always matched to exactly one applicant, assuming that the break state- ments (lines 8 and 13) never happen. (Hint: This is REALLY easy! Don't overthink it. But it's good practice on the structure of a loop-invariant/induction proof. If you phrase your answer as an induction, make sure it's an induction on the number of times the loop repeats.)
I nd many students are somehow afraid of loop invariant proofs, probably due to inexperience, but they are the easiest way to write these. So, I'll write this one rst using loop-invariant style, and then using induction style.
Loop-Invariant-Style Proof: When the code rst reaches the while loop on line 3, each employer is matched to exactly one applicant (its top-ranked applicant), because of the initialization on line 2. Assuming that each employer is matched to exactly one applicant at the top of the loop, the loop body always takes one employer and changes its matching applicant. Therefore, at the bottom of the loop, each employer is still matched to exactly one applicant. QED. (That's it! Easy!)
Induction-Style Proof: We prove that each employer is always matched to exactly one applicant by induction on the number of loop iterations k executed. Base Case: k = 0. Before the loop executes at all, each employer is matched to exactly one applicant (its top-ranked applicant), because of the initialization on line 2. Inductive case: Assume that each employer is matched to exactly one applicant after k iterations of the loop. On the k + 1st iteration, the loop body always takes one employer and
end for
(For anyone being really pedantic, we can assume the array indices are from 1 to n, or we can make
2
changes its matching applicant. Therefore, after the k + 1st iteration, each employer is still matched to exactly one applicant. QED.
These two styles are equally good, and equally formal. Choose whatever is easier and clearer for you.
4. For each applicant a, let matches(M,a) denote the set of employers who are matched with a in the matching M. Formally, matches(M,a) = {e ∈ E | (e,a) ∈ M}. Prove that for all a ∈ A, once matches(M,a) is non-empty, it never becomes empty again. (Hint: Again, this is a fairly easy loop- invariant/induction proof, although the way its phrased, you don't even need a base case. Just reason about the body of the loop.)
The loop body always removes one employer from matches(M, a) and adds one employer to matches(M, a′). Adding an element to a set can never make it become empty, so we need to worry only about matches(M,a). However, the while condition means that we always start the loop with at least 2 elements in matches(M,a), namely, e and e′, so removing one element can't make the set empty.
5. Prove that the break statements on lines 8 and 13 can't ever be triggered. (Hint: This will be very similar to the proof that in the original Gale-Shapley algorithm, no employer ever runs o the end of its applicant list. This is roughly Theorem 1.4 in the textbook. You'll also use parts 3 and 4 of this problem in your proof.)
I (Alan) got sloppy on this question, and an anonymous student caught the bug. Great job, Anony- mous! This resulted in a clarication posted to Piazza. The clarication is that you may assume part 3 proved that each employer is matched to at most one applicant, and this is true even with- out the assumption of no break statements. (The proof for this is almost as simple: Initially, each employer is matched with one applicant. On any loop iteration, either one employer's applicant is changed, so each is still matched with one applicant, or else an employer triggers the break and ends up matched with zero applicants, and the loop terminates. So, each employer is still matched with at most one applicant.)
To trigger the break statements on line 8 or 13, an employer e must have lost in the comparison on line 4 for every applicant a. That means for every applicant a, at some point e was in matches(M, a). By part 4, that means that every applicant still has at least 1 employer matched to it. But by part 3, each employer is matched to at most one applicant. Therefore, the n applicants must have at least n distinct employers matched to them, and none of those employers is e. This is a contradiction, since there are only n total employers, including e.
6. Prove that when the algorithm terminates, the result M is a perfect matching. (Hint: This should be a very short proof, based on part 5, the while loop condition, and what you proved in part 3 of this problem.)
By part 5, we know that the break statements never happen, so the only way for the algorithm to terminate is when the while condition becomes false. The while condition being false means that there does not exist any two employers matched to the same applicant. In other words, each applicant is matched to exactly one employer. By part 3, each employer is matched to exactly one applicant. That means M is a perfect matching.
7. Prove that when the algorithm terminates, the result M is stable. (Hint: We strongly recommend that you do a loop-invariant/induction proof, exactly like the worksheets in class. In particular, let Mk denotes the set of matches after k iterations of the loop, and for any applicant a where the set matches(Mk,a) is non-empty, dene favourite(Mk,a) to be a's highest-ranked employer in matches(Mk,a). Consider the matching Mk′, which we dene as the set of pairs (favourite(a),a) for all a ∈ A where matches(a) is non-empty. Can you prove Mk′ stable with respect to the employers and applicants that are matched in it?)
3
We prove that Mk′ is always stable with respect to the employers and applicants that are matched in it.
We'll write this induction-style, both to be compatible with the worksheets, and also to make it easier to compare the state of program before and after the loop body, using terms like M′ versus M′ .
k k+1 Base Case: k = 0. Before the loop rst executes, the code initializes M0 so that each employer gets its top choice. Therefore, M0′ is a perfect matching of some subset of the employers with their top-choice applicants. This means there can't be any instabilities in M0′ , since no employer would want to switch.
Inductive Case: Assume Mk′ is stable. The loop body has two cases (lines 58 and lines 1013), but the two cases are symmetric, so without loss of generality, let's just consider the rst case in lines 58. (The argument for the other case is the same, with e and e′ reversed.)
First, note that all pairs in Mk′ that do not involve a or a′ do not change as the result of the loop body executing.
Next, note that when line 6 executes, there is no change to Mk′ . This is because the matching for a in Mk′ is with favourite(M, a), and e′ can't be the favourite, because e >a e′.
Similarly, when line 7 executes, if e′ isn’t the new favourite of a′, then Mk′ doesn’t change after line 7, either. Hence, when e′ isn’t the new favourite of a′, then M′ = M′ and continues to be stable.
k k+1
All that’s left is the other case of line 7, when e′ is the new favourite of a′. This case is a bit trickier.
Let e′′ be the former favourite of a′. By part 3, we know that e′′ isn’t matched to anyone other than a′. So, once a′’s new favourite is e′, then e′′ isn’t matched in M′ and is no longer relevant when
k+1
computing the stability of M′ . So, the only change in the set of relevant employers and applicants
k+1
for evaluating the stability of M′ is that e′′ is replaced by e′. Hence, any new instability in M′
k+1
Note that since a′ has a higher-ranked employer in M′
k+1 than in M′ (since e′ >a′ e′′), there can’t be
must involve e′ or a′.
any new instabilities involving a′. (a′ was stable with e′′ before, so must be even more stable with e′
k
Can there be a new instability involving e′? No, because the employers are steadily moving down
their preference lists. Any applicant that e′ prefers to a′ must have already rejected e′ for some other
employer that they preferred. Therefore, in this case, M′ is stable as well. k+1
When the loop terminates, by part 6, Mk is a perfect matching, which implies that each applicant has exactly one matching employer. Therefore, at termination, Mk = Mk′ , so we terminate with a stable, perfect matching.
3 Measures of progress
When we analyzed the time complexity of the Gale-Shapley algorithm in class, we bounded the number of iterations of the while loop by observing that at every iteration, an employer makes an oer to an applicant this employer had not yet made an oer to. Since the total of number of (employer, applicant) pairs is n2, this allowed us to prove that the number of iterations of the loop is at most n2.
In this question, we present three algorithms (some of which you are already familiar with). In each case, you are asked to dene a measure of progress (we sometimes provided you with a hint), and then use it to bound the worst-case running time of the algorithm.
1. Algorithm InsertionSort(A) for pos ← 1 to n
key ← A[pos]
j ← pos – 1
while (j ≥ 0 and A[j] > key) do
afterwards.)
4
k+1
2.
A[j + 1] ← A[j]
j←j-1 A[j + 1] ← key
Measure of progress: the number of pairs i, j of positions in the array such that
i < j and A[i] > A[j]
Time complexity:
O(n2) because the number of such pairs is at most n = n(n − 1)/2 (every possible pair of positions 2
in the array), and because the number of these pairs decreases by 1 every time the statement A[j+1] ←A[j] is executed.
Algorithm Merge(A, first, mid, last) B ← []
i ← first
j ← mid + 1
while i ≤ mid and j ≤ last do if A[i] ≤ A[j] then
append A[i] to B
i←i+1 else
append A[j] to B
j←j+1 endif
while i ≤ mid do append A[i] to B i←i+1
while j ≤ last do append A[j] to B j←j+1
A[first … last] ← B
Measure of progress:
The number of elements added to the array B.
Time complexity:
O(last − first + 1) because there are only last − first + 1 elements in the portion of the array A that is being merged, and because every execution of the body of one of the three while loops moves an element into the array B.
5
4
else if Adjacent(P [i], S[S.top]) then
while S.top > 0 and not isReflex(S[S.top]) do
AddDiagonal(P [i], S[S.top − 1])
pop S
endwhile
push P[i] on S
Measure of progress:
The total number of elements of P that have been pushed onto the stack S.
Time complexity:
The for loop execute n − 2 times, and in each iteration we push at most 2 elements onto the stack S. Taking the two push operations that come before the loop into account, this means we can push at most 2 + 2(n − 2) = 2n − 2 items onto S. Every iteration of the body of one of the nested while loops pops an item from S. Since we can not pop more items than we have pushed, the maximum number of iterations of the nested while loops is thus also 2n − 2. Therefore the for loop runs in O(n) time.
The remainder of the algorithm (the part before the for loop) runs in O(n log n) time because of the need to sort P by decreasing y value. The total running time of the algorithms is thus in O(n log n).
Faster, Same, Slower or Neither
3.
In the following description, assume that the functions Adjacent, AddDiagonal and isReflex all run in constant time.
Algorithm MonotoneTriangulation(P)
//
// P is an array of pairs (x, y).
// S is a stack implemented as an array. S.top is the index of S’s top element. //
sort P by decreasing y to get P[0], P[1], …
S ← new stack
push P[0] on S
push P[1] on S
for i ← 2 to n-1 do
if Adjacent(P [i], S[0]) then
newtop ← S[S.top] while S.top > 0 do
AddDiagonal(P [i],
pop S
endwhile
pop S
push newtop on S push P[i] on S
S[S.top])
The pairs of functions below represent algorithm runtimes on an undirected, connected graph with n vertices and m edges, and a simple path (one that does not go through any vertex twice) of length k in that graph. ASSUME n ≥ 2. For each pair, ll in the circle next to the best choice of:
LEFT: the left function is big-O of the right, i.e., left ∈ O(right) RIGHT: the right function is big-O of the left, i.e., right ∈ O(left)
6
SAME: the two functions are Θ of each other, i.e., left ∈ Θ(right)
INCOMPARABLE: none of the previous relationships holds for all allowed values of n, m and k.
Do not choose LEFT or RIGHT if SAME is true.
Left Function
5n
nlogn
mlogm
n
kn
n+k
Right Function
Answer
m LEFT RIGHT
SAME
INCOMPARABLE m LEFT
RIGHT
SAME INCOMPARABLE
mlogn LEFT RIGHT
SAME
INCOMPARABLE k LEFT
RIGHT
SAME INCOMPARABLE
m LEFT RIGHT
SAME
INCOMPARABLE m LEFT
RIGHT
SAME INCOMPARABLE
Explanations:
1. m≥n−1,andso5n∈O(m). Howeverm∈/O(5n)becausemcanbeaslargeasn=n(n−1)/2.
2
2. m can be as small as n−1, and so nlogn ∈/ O(m). However m can also be as large as n = n(n−1)/2 2
and so m ∈/ O(n log n).
3. Since n−1 ≤ m ≤ n(n−1)/2, log(n−1) ≤ logm ≤ log(n(n−1)/2), which means that log(n−1) ≤
logm≤2logn−1. Hencemlogm∈Θ(mlogn). 7
4. Weknowthat1≤k