Page 255 - Discrete Mathematics and Its Applications

234 3 / Algorithms

21. Find all pairs of functions of the same order in this 31. Find all valid partners for each man and each woman if
2
2
n
2
2
list of functions: n + (log n) , n + n, n + log 2 + 1, there are three men m 1 , m 2 , and m 3 and three women w 1 ,
2
3
3
(n + 1) − (n − 1) , and (n + log n) . w 2 , w 3 with these preference rankings of the men for the
women, from highest to lowest: m 1 : w 3 , w 1 , w 2 ; m 2 : w 3 ,
22. Find all pairs of functions of the same order in this list of w 2 , w 1 ; m 3 : w 2 , w 3 , w 1 ; and with these preference rank-
2
2
2
2
2
n
n
2n
functions n + 2 , n + 2 100 , n + 2 , n + n!, n + 3 , ings of the women for the men, from highest to lowest:
2
2
and (n + 1) .
w 1 : m 3 , m 2 , m 1 ; w 2 : m 1 , m 3 , m 2 ; w 3 : m 3 , m 2 , m 1 .
n
23. Find an integer n with n> 2 for which n 2 100 < 2 . ∗ 32. Show that the deferred acceptance algorithm given in the
24. Find an integer n with n> 2 for which (log n) 2 100 < √ n. preamble to Exercise 61 of Section 3.1, always produces
a male optimal and female pessimal matching.
2
n
n
∗ 25. Arrange the functions n , (log n) , n 1.0001 , (1.0001) , 33. Define what it means for a matching to be female optimal
√
2 log 2 n , and n(log n) 1001 in a list so that each function and for a matching to be male pessimal.
is big-O of the next function. [Hint: To determine the ∗ 34. Show that when woman do the proposing in the deferred
relative size of some of these functions, take logarithms.] acceptance algorithm, the matching produced is female
optimal and male pessimal.
2
n
n
2
∗ 26. Arrange the function 2 100n ,2 ,2 ,2 , n log n , In Exercises 35 and 36 we consider variations on the problem
n!
2
n log n log log n, n 3/2 , n(log n) 3/2 , and n 4/3 (log n) in a of finding stable matchings of men and women described in
list so that each function is big-O of the next function. the preamble to Exercise 61 in Section 3.1.
[Hint: To determine the relative size of some of these
∗ 35. In this exercise we consider matching problems where
functions, take logarithms.]
there may be different numbers of men and women, so
∗ 27. Give an example of two increasing functions f (n) and that it is impossible to match everyone with a member of
g(n) from the set of positive integers to the set of posi- the opposite gender.
tive integers such that neither f (n) is O(g(n)) nor g(n) a) Extend the definition of a stable matching from that
is O(f (n)). given in the preamble to Exercise 60 in Section 3.1
1
0
k
28. Showthatifthedenominationsofcoinsare c ,c ,...,c , to cover the case where there are unequal numbers of
men and women. Avoid all cases where a man and a
where k is a positive integer and c is a positive integer,
c> 1, the greedy algorithm always produces change us- woman would prefer each other to their current sit-
ing the fewest coins possible. uation, including those involving unmatched people.
(Assume that an unmatched person prefers a match
29. a) Use pseudocode to specify a brute-force algorithm that with a member of the opposite gender to remaining
determines when given as input a sequence of n pos- unmatched.)
itive integers whether there are two distinct terms of b) Adapt the deferred acceptance algorithm to find sta-
the sequence that have as sum a third term. The algo- ble matchings, using the definition of stable matchings
rithm should loop through all triples of terms of the from part (a), when there are different numbers of men
sequence, checking whether the sum of the first two and women.
terms equals the third. c) Prove that all matchings produced by the algorithm
b) Give a big-O estimate for the complexity of the brute- from part (b) are stable, according to the definition
force algorithm from part (a). from part (a).
∗ 36. In this exercise we consider matching problems where
30. a) Devise a more efficient algorithm for solving the prob-
some man-woman pairs are not allowed.
lem described in Exercise 29 that first sorts the in-
put sequence and then checks for each pair of terms a) Extend the definition of a stable matching to cover
whether their difference is in the sequence. the situation where there are the same number of men
and women, but certain pairs of men and women are
b) Give a big-O estimate for the complexity of this al-
forbidden. Avoid all cases where a man and a woman
gorithm. Is it more efficient than the brute-force algo-
would prefer each other to their current situation, in-
rithm from Exercise 29?
cluding those involving unmatched people.
Suppose we have s men and s women each with their prefer- b) Adapt the deferred acceptance algorithm to find stable
ence lists for the members of the opposite gender, as described matchings when there are the same number of men
in the preamble to Exercise 60 in Section 3.1. We say that a and women, but certain man-woman pairs are forbid-
woman w is a valid partner for a man m if there is some sta- den. Be sure to consider people who are unmatched at
ble matching in which they are paired. Similarly, a man m is a the end of the algorithm. (Assume that an unmatched
valid partner for a woman w if there is some stable matching person prefers a match with a member of the opposite
in which they are paired.A matching in which each man is as- gender who is not a forbidden partner to remaining
signed his valid partner ranking highest on his preference list unmatched.)
is called male optimal, and a matching in which each woman c) Prove that all matchings produced by the algorithm
is assigned her valid partner ranking lowest on her preference from (b) are stable, according to the definition in part
list is called female pessimal. (a).