HOMEWORK 6

Background material: Ch. 12.

Due October 29th:

• 6.1: CLR Exercise 12.3-1 (pg 231).

• 6.2: Use a hash table to compute the mode of a list of n numbers in expected O(n) time.

• 6.3: CLR Exercise 12.2-6 (pg 226). [Extra credit.]

• 6.4: For a set of n boys and n girls with rank-order lists, give an O(n²) algorithm to check if a given marriage is stable.

• 6.5: Argue that, if the boy-optimal marriage and the girl-optimal marriage are the same marriage, then there is only one stable marriage. [Extra credit.]

• 6.6: Use potential function analysis to analyze the matching algorithm. Assume rank takes O(1), so you should get a O(n²) bound. [Extra credit.]