1. You are a matchmaker, and a group of n people come to you for help. Each person gives you the name of a person within the group whom they'd like to date; for example, Romeo would like to date Juliet. Note that there may be some people - the Wolfman, for example - whom nobody wants to date; also, there may be some people - the Richest Person in the World, for example, whom more than one person wants to date.

   Your job is to form the largest subgroup of people with the following two properties:

   1. if A is in the subgroup and A wants to date B, then B is in the subgroup too.

   2. For each person B in the subgroup, there is exactly one person A who wants to date B

   Solve using induction.

   ---

   Suppose the algorithm max-match(S) accepts S, the set of people, and returns the largest subset of S that meets the two requirements above. How does max-match() work?

   Induct over the number of people in S:

   Hyp: P(n) = max-match(S) correctly solves the problem when |S| = n.

   The base case occurs when S is empty, in which case max-match(S) returns the largest subset of the empty set; that is, the empty set itself:

   Bas: P(0) holds

   Now suppose P(i) holds for some i >= 0 and consider P(i + 1). The tricky part of this induction is how to go from |S| = i + 1 to |S| = i: which person should be removed from S?

   There are two cases: remove a person that belongs in the answer, or remove a person that doesn't belong in the answer. The first case is hard; in fact, finding the people to keep is the problem max-pairs() is trying to solve. The second case is easy: if nobody in S wants to date person j, then person j can't be part of the answer and should be removed from S.

   Ind: Assume P(i) holds for some i >= 0 and consider P(i + 1). Pick from S the person j that no other person in S wants to date. There are two cases to consider:

   1. Such a person j exists. Then throw j out of S to reduce the number of people in S to i. By the inductive hypothesis, max-pairs(S) returns the correct answer.

   2. No such person exists; that is, every person a in S has a person b in S such that b wants to date a. Because each person can date exactly one other person, property 2 holds. Also, because only those people whom nobody wants to date are thrown out of S, property 1 holds too. S is the largest set meeting both properties and it should be returned by max-pairs(S).

   Because P(i + 1) holds if P(i) does, max-pairs() works as expected.

   ---

2. You are still, a matchmaker and a group of n people come to you for help. Each month, every member of the group must date every other member of the group. One person on a date is the inviter, who pays for the date, and the other person is the invitee.

   The group hands you an n x n boolean matrix M. M[i, j] is true if person i invited person j in a date last month (in which case M[j, i] is false) and false otherwise (in which case M[j, i] is true because every pair of people must date once a month and one of the two people must be the inviter).

   Your job is to form a sequence (p₁, p₂, ..., p_n) of the n members of the such that, for 1 <= i < n, person p_i invited person p_{i + 1} on a date last month

   Solve using divide and conquer.

   ---

   This problem is a thinly disguised sorting problem. The answer below is based on merge sort; a number of people gave answers based on insertion or selection sorts. Let the n people be numbered 1 through n and assume n > 1. The idea is to divide the people into to equal (more or less) groups, form each group into a chain, and then merge the two chains into a single chain using the invites relation.

   [int] chain(b, e)
     if b = e
       return [b]
     m <- floor((e + b)/2)
     c1 <- chain(b, m)
     c2 <- chain(m + 1, e)
     c <- []
     while c1 != [] and c2 != []
       if M[head(c1), head(c2)]
         c <- c || [head(c1)]
         c1 <- tail(c1)
       else
         c <- c || [head(c2)]
         c2 <- tail(c2)
     return c || c1 || c2
   

   The amount of work done by chain() on n people is T(n), which is 2T(n/2) for the divide and conquer part and O(n) for the merging part:

   T(n) = 2T(n/2) + O(n)

   T(n) unrolls into an O(nlog n) solution.

   ---

This page last modified on 2 May 2000.