Your job is to form the largest subgroup of people with the following two properties:
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) =The base case occurs whenmax-match(S)correctly solves the problem when|S|= n.
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) holdsNow 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 fromSthe personjthat no other person inSwants to date. There are two cases to consider:
- Such a person
jexists. Then throwjout ofSto reduce the number of people inSto i. By the inductive hypothesis,max-pairs(S)returns the correct answer.- No such person exists; that is, every person
ainShas a personbinSsuch thatbwants to datea. 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 ofS, property 1 holds too.Sis the largest set meeting both properties and it should be returned bymax-pairs(S).Because P(i + 1) holds if P(i) does,
max-pairs()works as expected.
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 (p1, p2, ..., pn) of the n members of the such that, for 1 <= i < n, person pi invited person pi + 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.