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!

____________________________________________________________________________________________