In the Design and Analysis of Algorithms, 
both this course and its predecessor, 
we've covered a lot of famous algorithms. 
We've covered a lot of fundamental data 
structures. 
We've covered lots of killer 
applications. 
And despite the fact that I've tried to 
use our time together in the optimal way, 
giving you the most bang for the buck, 
there are fundamental topics we have not 
had a chance. 
To cover. 
In these final few videos, I want to talk 
about things we didn't talk about. 
I have a few goals. 
The first goal is to give you a little 
bit of literacy and a few more techniques 
so at least you've heard of things like 
bypar type matching, and the maximum flow 
problem, and your aware that there are 
good algorithms for those sorts of 
problems. 
Secondly, I want to get you excited to do 
a little bit more study either through 
further courses or on your own. 
And indeed generally the topics that I'll 
mention in these final few videos are 
covered in your more comprehensive 
textbooks. 
On algorithms. 
Finally I hope to convey something that I 
mention in passing, in the past, is that 
algorithms is not a oscified field. 
Rather, it's a vibrant area of research. 
There's still lot's of things about 
fundamental problems of models that we 
don't get. 
Understand. 
Let's get the ball rolling with a very 
fun, classical problem known as stable 
matching. 
We're going to think of stable matching 
as a graph problem and there's going to 
be two sets of nodes, two sets of 
vertices, U and V. 
For historical reasons, we will call 
these sets the men and the women, 
respectively. 
A non-essential assumption that will make 
for simplicity is that these 2 sets of 
nodes have equal cardinality. 
Call that common size N. 
So for example, maybe N equals 3 and we 
can call the first set of nodes A, B and 
C. 
And the second set of nodes D, E and F. 
Now what's really important about the 
stable matching problem is that every 
node has preferences, there are things 
that advance more than others. 
Specifically each node in U has a rank 
list of the nodes in V, each node in V 
has a rank list of the nodes in U. 
So in this example maybe A, B, and C are 
all on the same page. 
They all agree that D is really the best 
node, it's better than E, but E is 
definitely better than F. 
That is maybe every single node on the 
left hand side has the rank listed D, 
followed by E, followed by F. 
By contrast, maybe there's heterogeneous 
preferences amongst vertices in capital 
V. 
Maybe D thinks a is better than B is 
better than C. 
While E prefers B to C to A. 
And finally, F prefers C to A to B. 
So what might these nodes and these 
ranked lists represent? Well, imagine for 
example that one set is colleges and the 
other set is applicants, recent high 
school graduates. 
Each college has a ranking of the 
applicants based on things like test 
scores, grades and the fit that student 
is for the college. 
And each student similarly has a ranking 
over the colleges of which one's prefers 
to go to. 
Do over others. 
As another example you might think about 
medical residents that is people who just 
finished medical school looking for 
residency and the other side being 
hospitals. 
Again hospitals are going to have a 
preference over which recent graduates 
they accept as residents, residents, 
potential residents of course have 
preferences over which hospital they get 
assigned to. 
So given this data, 2 sets of nodes, and 
these rank lists we're interested in 
computing a stable matching. 
So what's a stable matching? Well, first 
of all, it better give you a perfect 
matching. 
And a perfect matching means that each 
node of the left, each node of U is 
matched to exactly one node of V and vice 
versa. 
In addition to being a perfect matching, 
it should also be stable in the sense 
that there should be no Blocking pair. 
What that means, is that if you look at 
any pair of nodes, little u from capital 
u, little v from capital v, if little u 
and little v are not matched, there 
better be a good reason for them not 
being matched. 
Specifically little u better strictly 
prefer Who it is matched to, call that V 
prime, to this alternate V, or if that's 
not the case, it better be that little v 
strictly prefers the node it's matched 
to, call it U prime, compared to the 
alternative. 
Little u. 
So what's the motivation for this 
definition? Well think about any perfect 
matching that fails this stability 
property. 
You're really asking for trouble for that 
kind of matching. 
Specifically u with its wandering eye 
will spy v and it prefers v over v node v 
prime to which It was a sign. 
Similiary, V is going to return that 
gaze. 
V prefers U by assumption that this 
stability property fails over the node U 
prime to which it was matched, so U and V 
are going to have an incentive to 
essentially elope and disrupt this 
Imagine for example that u is a student 
and V is a college. 
And you have a matching that fails the 
stability property. 
Then, this pair this student and this 
college has an incentive to do a sort of 
back room deal after the fact. 
U might want to withdraw its commitment 
from its assigned college, V-prime to try 
and get into V instead. 
And V to college actually wants to 
sort of withdraw its offer from its 
student, U prime, they give it to U 
instead. 
So that's an unstable matching, but as 
long as there's no blocking pair of this 
form, and for every pair which is not 
matched together there's a good reason 
for it, then we deem it a stable Stable 
matching. 
Let me tell you about an extremely 
elegant and justly famous algorithm for 
computing a stable matching, the 
Gale-Shapley Proposal Algorithm. 
Lloyd Shapely was one of the recipients 
of the 2012 Nobel Prize in economics, in 
large part for this algorithm. 
Had David Gale still been alive, he 
surely would have been a co-recipient of 
that Nobel Prize as well. 
Let me explain the algorithm in an 
example, then I'll give you the general 
psudeocode. 
We start with the empty matching, with 
nobody matched with anybody else. 
And as long as there's some man, some 
node on the left hand side which isn't 
matched to some woman. 
We pick an arbitrary unattached man and 
we let it propose to a woman of its 
choice. 
So we might start for example with The 
man C. 
C says, well, my favorite woman is D, so 
let me start by proposing to the woman D. 
Now D isn't necessarily very impressed 
with C, you've noticed C is last in these 
preference list, but with a lack of other 
proposals at the moment, the node D 
tentatively accepts this proposal from C. 
Now we proceed to the next iteration of 
the wow loop, we look for a man that is 
unattached, so maybe we pick B. 
B now gets its shot at proposing to its 
favorite woman. 
In this case it is also D. 
So now the node D has a bit of leverage 
it has two competing offers from the 
nodes B and C and of course it retains 
the offer from the preferred suitor in 
this case D prefers D to C so the edge 
between C and D gets deleted and replaced 
with the edge between B and D. 
So now both of them at A and C are 
unattached. 
Perhaps in the next iteration we let the 
node A gets its shot. 
It again proposes to the node D, and 
again D prefers A to B, so the edge 
between A and D is going to replace the 
edge between B and D. 
So now we again have 2 on hatched men B 
and C, lets say we pick C next so C gets 
to propose to what ever women it wants 
and D is its favorite but it is already 
being rejected by D and in the algorithm 
men will never re-propose to a women who 
has previously rejected him. 
So next on C's list is the women E and so 
E has that not had any other offer so E. 
He tentatively accepts the proposal from 
C. 
But now, once B gets a chance, B will 
also propose next to E, that's B's next 
favorite and it's already been rejected 
by D. 
And E prefers B to C, so we will replace 
the edge between C and E with the edge 
between B and E. 
And so now, finally, the man C is the 
only one that remains unattached and it 
has no choice but to propose to its final 
option the node F. 
F actually happily accepts that because c 
is on the top of f's list. 
And that leaves us with the matching That 
matches A with D, B with E, and C with F. 
This is clearly a perfect matching. 
I'll let you check that's is also a 
stable matching. 
Having traced through this example, I 
hope that the pseudocode for the general 
algorithm will not surprise you. 
So we have a main y loop. 
In each iteration we pick some man who is 
not yet engaged to any woman, call that 
man u. 
U then proposes to his favorite woman, 
the top ranked woman with the constraint 
that he will not propose a second time to 
any woman who has already rejected him. 
Each woman then behaves in the obvious 
way which is to keep track of all of the 
suitors, all of the men that have 
proposed to her and to retain as a 
tentative engagement only the proposal 
from their favorite, that is highest 
ranked suitor. 
Notice this algorithm maintains the 
invariant that the current set of 
engagements is a matching. 
Not necessarily a perfect matching, but a 
matching. 
That is, at any given time a man is 
engaged tentatively to, at most, one 
woman. 
And every woman is tentatively engaged 
to, at most, one. 
The Gale-shapley theorem states that, not 
only does this algorithm terminate 
quickly, not only does it terminate 
quickly with a perfect matching. 
But in fact, it terminates quickly, 
namely, in a quadratic number of 
iterations at most. 
With a stable match. 
In particular, this theory, this 
algorithm provides constructive proof 
that a stable matching always exists, no 
matter what the preference of the node 
are. 
A highly non-obvious fact. 
The proof of the Gale-Shapley theorem is 
as elegant as the algorithm. 
Let me show it to you now. 
So first of all, why does the algorithm 
converge in a quadratic number of 
iterations? Well, no man proposes to a 
woman twice. 
Therefore, each man makes at most n 
proposals. 
There are only n men so that's the most 
n^2 proposals over all. 
Secondly, when the Gale-Shapley algorthym 
terminates it does show with a perfect 
matching. 
Indeed it's a stable matching, but let's 
just for the moment prove that it's a 
perfect matching. 
To, to see this let's suppose the 
contrary. Let's suppose that when it 
halts, it does not halt with a perfect 
match. 
That means, in particular, some man is 
assigned to know woman. 
How could that have happened? Well it 
must have been that the man fell off of 
his ranked list. 
He proposed to every single one of the n 
women and was rejected by all of them . 
So how could this have happened? 
Well, notice that for a man to be 
rejected by a woman, it must be that the 
woman has some other offer from some 
other man that she likes better. 
That is, rejections happen only by a 
woman who is engaged to somebody else. 
So by virtue of this man being rejected 
by all n women, all n women got engaged 
at some point in the algorithm. 
Moreover, if you inspect the algorithm, 
you'll notice that once a woman is 
engaged to somebody, she will remain 
engaged forever more. 
The only thing that changes, is the woman 
is engaged to men that she likes better 
and better as the alogorithm proceeds. 
So a man rejected by everybody implies 
that all women get engaged at some point 
in the algorithm which means they are all 
engaged at the end of the algorithm. 
But there's an equal number of men and 
women. 
So there's no way all women are engaged 
at the end and some man is not engaged. 
If all women are engaged, all men must be 
engaged. 
As well. 
Finally, why is the perfect matching, 
computed by the Gale-Shapley proposal 
algorithm, not just perfect, but more 
generally, stable? To see why this is 
true, let's prove that there's no 
blocking pair. 
That is, let's consider an arbitrary 
unmatched man u and woman v. 
Now either, the man, u, proposed to the 
woman, v, at some point in the proposal 
algorithm, or he didn't. 
Let's treat those two cases separately. 
So let's first suppose that at no point 
in the algorithm did the man u, propose 
to the woman v. 
So, what's the behavior of a man in the 
proposal algorithm? Well a man simply 
proposes to the women on his list one at 
a time in turn as necessary. 
And the man, the woman to whom a man 
winds up matched at the end of the 
algorithm is the last woman to whom he 
proposed. 
So if the man u never got around to 
proposing to the woman v, that just means 
that he never searched that far down in 
his preference list. 
And he wound up, at the conclusion of the 
algorithm, matched with the woman he 
prefers to the woman v. 
And so that's sufficient to say, to claim 
that uv is not a blocking pair. 
Suppose, on the other hand, that you did 
propose the woman, v, at some point in 
the algorithm. 
Why did they not wind up matched? Well, 
it must be because the woman, v, got a 
preferred offer, an offer from some man 
that she prefers To the man you. 
Now something we mentioned earlier, is 
over the course of the algorithm, a women 
just winds up being engaged to men that 
she prefers more and more. 
So that any point she winds up engaged to 
a man she prefers to you, then the end of 
the algorithm she will And be engaged, 
matched with a man that she prefers to u. 
And again, that implies that uv is not a 
blocking pair. 
Since uv was arbitrary, this is a stable 
matching. 
That completes the proof of the 
Gale-Shapley Theorem.