Massachusetts Institute of Technology Handout 20 6.042J/18.062J: Mathematics for Computer Science October 2, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 4

1. Efficiency of Euclid’s algorithm.

(a) Show that Euclid’s GCD algorithm uses at most 2 log_{2} x modulo operations. [Use derived variables]

(b) Let F_{n} denote the n^{th} Fibonacci number. Show that:

i. If 2 ≤ x ≤ F_{n} then the algorithm uses at most n−2 modulo operations. ii. For n ≥ 2, F_{n} ≥ (\frac{3}{2})^{n−2}. iii. Using the previous two results show that Euclid’s algorithm actually

uses at most 1.71 log_{2} x modulo operations if x ≥ 2.

2. Choosy mating.

(a) We have the mating problem again, but now both boys and girls are more choosy about their partners. That is, among a set of n boys and n girls, each boy is unwilling to drop below his k^{th} choice and each girl is unwilliling to below her m^{th} choice. So it is possible that some of them are not married. How many pairs can we be sure of having in general ?

(b) What if only the boys were choosy, i.e., the girls are willing to marry anyone (they still have a ranked list of preferences), but the boys will not go below their k^{th} choice ? How many pairs will the algorithm from class (TMA) assure us ?