30E a) Devise a more efficient algorithm for solving the

Chapter 3, Problem 30E

(choose chapter or problem)

?30E a) Devise a more efficient algorithm for solving the problem described in Exercise 29 that first sorts the input sequence and then checks for each pair of terms whether their difference is in the sequence. b) Give a big-?O estimate for the complexity of this algorithm. Is it more efficient than the brute-force algorithm from Exercise 29? Suppose we have a men and ¿' women each with their preference lists for the members of the opposite gender, as described in the preamble to Exercise 60 in Section 3.1. We say that a woman w is a valid partner for a man m if there is some stable matching in which they are paired. Similarly, a man ?m is a valid partner for a woman ?w if there is some stable matching in which they are paired. A matching in which each man is assigned his valid partner ranking highest on his preference list is called male optimal, and a matching in which each woman is assigned her valid partner ranking lowest on her preference list is called female pessimal.