U.C. Berkeley – CS70: Discrete Mathematics for Computer Science Problem Set 2Lecturer: Luca Trevisan Due February 6, 2007 at 2:30pmProblem Set 21. Simple Induction (5 pts)Prove that for every n ≥ 2,q1 +p1 + . . .√1 (n square roots) is irrational.2. Recursion and proofs (5 pts)Let the function, g, be defined on the natural numbers r e c ursively as follows: g(0) = 0, g(1) = 1, andg(n) = 5g(n − 1) − 6g(n − 2), for n ≥ 2.Prove that ∀n ∈ N, g(n) = 3n− 2n.3. Making big rocks into little rocks (5 pts)One day, you find a shady-looking flyer on Sproul that advertises an undergraduate research positionin the Stanfor d geology department. After you make your way down to the Fa rm, Dr. Hoover, theprofessor in charge, hands you the following assignment to keep you busy for the first year, complainingthat none of the Stanford undergrads have been able to help him:You are given a single large pile of pebbles to start w ith. Every day, you have pick one pile of pebblesand split it into two smaller piles any way you wish. Then, you have to count the number of pebblesin each of the two new piles you just crea ted (k and m), and write down the product k ×m in your labnotebook. Of cour se, over time, you end up with more and mor e piles which get smaller and smaller.You get to stop when each pebble is in its own pile. Once you stop, add up all the numbers you wrotedown and report them to Dr. Hoover. See Figure 1 for an example of the process.Convince Dr. Hoover (and his funding ag e ncy) that this1is a pointless exercise: no matter how yousplit the piles, your answer will come out to n(n−1)/2, where n is the number of p e bbles in the originalpile (which you can just count on the first day).4. Stable Marriage (aka s table matching)(a) (5 pts) For the following instance of the stable marriage problem:Man highest→lowest1 B A C2 C B A3 A C BTable 1: Men’s preference listWoman highest→lowestA 1 2 3B 2 3 1C 3 1 2Table 2: Women’s preference listi. List the rogue couples in the pairing (1, C), (2, B), (3, A).ii. List all the possible stable pairings (note that a s ingle run o f the algorithm from class willonly reveal one; there may be others).(b) (3 pts) Run the traditional propose and reject algorithm on the following example:Man highest→lowest1 A B C D2 B C A D3 C A B D4 A B C DTable 3: Men’s preference listWoman highest→lowestA 2 3 4 1B 3 4 1 2C 4 1 2 3D 1 2 3 4Table 4: Women’s preference list1The research assignment, not this homework problem!Day: Pile-splitting operation: Write down:Day 1: 3 × 2 = 6Day 2: 1 × 1 = 1Day 3: 1 × 2 = 2Day 4: 1 × 1 = 1Day 5: Total: 6 + 1 + 2 + 1 = 10Figure 1: An example rock procedure for Pr oblem 3 with n = 5. Bonus (0 pts): what are those
View Full Document
Unlocking...