Source code online books for professionals by professionals

eaGer SUItOrS aND StaBLe MarrIaGeS
there is, in fact, one classical matching problem that can be solved (sort of) greedily: the stable marriage 
problem. the idea is that each person in a group has preferences about whom he or she would like to marry.  
We’d like to see everyone married, and we’d like the marriages to be stable, meaning that there is no man who 
prefers a woman outside his marriage who also prefers him. (to keep things simple, we disregard same-sex 
marriages and polygamy here.)
there’s a simple algorithm for solving this problem, designed by david Gale and Lloyd shapley. the formulation is 
quite gender-conservative but will certainly also work if the gender roles are reversed. the algorithm runs for  
a number of rounds, until there are no unengaged men left. each round consists of two steps:
1.  each unengaged man proposes to his favorite of the women he has not yet asked.
2.  each woman is (provisionally) engaged to her favorite suitor and rejects the rest.
this can be viewed as greedy in that we consider only the available favorites (both of the men and women) right 
now. You might object that it’s only sort of greedy in that we don’t lock in and go straight for marriage; the women 
are allowed to break their engagement if a more interesting suitor comes along. even so, once a man has been 
rejected, he has been rejected for good, which means that we’re guaranteed progress and a quadratic worst-case 
running time.
to show that this is an optimal and correct algorithm, we need to know that everyone gets married and that the 
marriages are stable. once a woman is engaged, she stays engaged (although she may replace her fiancé).  
there is no way we can get stuck with an unmarried pair, because at some point the man would have proposed 
to the woman, and she would have (provisionally) accepted his proposal.
how do we know the marriages are stable? Let’s say scarlett and stuart are both married but not to each other. 
Is it possible they secretly prefer each other to their current spouses? No. If this were so, stuart would already 
have proposed to her. If she accepted that proposal, she must later have found someone she liked better; if she 
rejected it, she would already have a preferable mate.
although this problem may seem silly and trivial, it is not. For example, it is used for admission to some colleges 
and to allocate medical students to hospital jobs. there are, in fact, entire books (such as those by donald Knuth 
and by dan Gusfield and robert W. Irwing) devoted to the problem and its variations.