Thursday, May 15, 2008 at 23:54
I had my first class as a UofT student tonight. Of course, this begs the question: “What if … Jeffrey Lo had accepted the UofT offer of admission instead of going off to Queen’s?” I’ll tell you what, the commute would kill me.
I went down to pick up my TCard and strolled around campus a bit. The buildings on the St. George campus are much nicer (and taller) than the ones at Queen’s. There’s a certain energy to the campus that’s non-existent in Kingston. I was surprised that there were so many students still around. Moreover, there were pretty girls sitting outside my class, but alas, they were taking English, not Algorithm Design.
Anyway, Mr. David presented us a problem. Given two sets, M and W (men and women), our task was to create marriages based on each person’s preference list for members of the other set. Pretty relevant stuff.
One solution that David suggested was this:
Let there be an engagement period. All men start out free.
While there exists, in the set of Men,
men who are free and haven't proposed to each woman in W,
choose any such man m to propose to his highest ranked w.
m proposes to w.
If w is free, they become engaged and form (m,w).
Else (meaning w is not free, i.e. engaged to another man m') then
If w prefers m' to m,
m remains free.
Else w prefers m over m',
thus forming (m,w) and m' becomes free.
End while.
From this, it follows that every woman remains engaged from the point of first proposal. Also, the sequence of men she gets engaged to only gets better as more men attempt to win her heart. Sadly, the men’s situation only gets worse over repeated proposals. Consolation: the output is a perfect matched set!
