Algorithm Design Techniques Fall 2009
COMP-360
Assignment 1
Due: Monday September 21, 5pm
Assignments to be left in the
drop-off box, Trottier 3rd floor, near consultants area.
Late assignments -10% per
day, including
weekends.
If you work closely with someone else, indicate the person's name(s)
on your homework.
The final write-up of each assignment must, however, be your own work.
1. (Stable Matching). Suppose
there are m women and n men, and m < n. Assume that each man prefers
to be married than single.
Consider two modified versions of the Gale-Shapley algorithm, where the
men propose to the women:
A1: The algorithm terminates when each woman receives a proposal.
A2: The algorithm terminates when each man either has a partner, or has
no-one left to propose to.
In each case, either prove that a stable solution is always reached, or
show an unstable solution may occur.
2. Text, P. 25, problem 6.
3. Read the handout
on Selection Problems (see Sep 10 lecture). Let G=(V,E) be an
undirected graph.
P1: Let S=V, and call a subset B of S admissible
if there is some matching M in G that contains all the vertices in B (M
may contain other vertices as well).
(a) Show that P2 and P3 hold for this problem, and so Greedy solves the
weighted version of this problem.
(b) Invent some interpretation of the weighted version of this problem
(eg. marriage, assigning jobs to students, ....)
4. Text, P. 194 problem 13. Be
sure to prove the correctness of your algorithm!
____________________________________________________________________________________________