Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science October 3, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 5

Due: 2:35pm in lecture, Thursday, October 12, 2000.

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study: Simple algorithms and pseudocode Read: Rosen Section 2.1 Self-study problems (not to be handed in): 1, 3, 5, 7, 9, 11, 19

—————————————————————————–

Reading: Lecture notes; Rosen 2.1, 3.5 (skim)

Policy on collaboration If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

Problem 1 In ancient times, the downtown section of Verona was laid out in a 1000 by 1000 meter square. Romeo lived at grid point (0, 0) of the square, and Juliet lived at grid point (0, 1000). Of course, Romeo and Juliet wanted to meet, at exactly the same point in the square. However, both were restricted by their rather strange families to move according to very particular rules: Romeo could only move 3 units, parallel to either the x axis or y axis or at a 45 degree angle to both axes. Juliet could only move 3 units, and only parallel to either the x axis or y axis.

(a) Model Romeo and Juliet and their possible moves as a (single) state machine.

(b) Can they meet, by some sequence of moves?

(c) If your answer to ... is yes, then give such a sequence of moves. If your answer to ... is no, then prove formally that they cannot, by finding and proving an appropriate invariant of your state machine.

Problem 2 The following weird algorithm is used to multiply two natural numbers x and y using only multiplication and division by 3. The answer is accumulated in variable a; variables r and s are for temporary storage. [[[Base this on Problem 5 of last term’s pset 4. But now there are three cases instead of two: if s = 0 mod 3 then multiply r by 3 and divide s by 3 if s = 1 mod 3 then add r to a, multiply r by 3, divide s-1 by 3, if s = 2 mod 3 then add 2r to a, multiply r by 3, divide s-2 by 3,

The parts of the question can be the same: (a) model... (b) list steps of some suitable execution ... you can use inputs x = 5 and y = 10, e.g. (c) invariant—same as before? (d) termination Problem 3 [[[This one needs writing in nice English. I’ll just outline it.]]] Recall the double induction example from lecture... Recast this as a nondeterministic algorithm, where the start state has all the (n,0) and (0,k) entries already filled in (set to 1). (Yes, I know that’s an infinite amount of information. That’s allowed.) The algorithm has only one kind of step: for any location (n, k) that isn’t filled in, but for which both the left location (n, k − 1) and the lower location (n − 1, k) are filled in, fill in the new location with the sum.

(a) The main correctness property we are interested in is that any value that is filled in is in fact equal to n! / k! (n-k)! Prove this using the Invariant Theorem.

(b) What can you say about termination?

Problem 4 [[[caching problem from last year’s pset 4.5, problem 6. About hybrid caching scheme.]]]

[[[I’m not happy with using so many problems (3) from last year’s pset 4.5. If we could think of some variations on these, that would be nice.]]]

Problem 5 [[[Fix up English.]]] Suppose that n girls and m boys show up one evening for MIT Ballroom Dancing, where n > m. Suppose they use the same matching algorithm that we studied in class. What happens? Prove your answer.

Problem 6 [[[Problem 7 from spring 00 pset 4.5 [[[This is hard. May want some hints...???]]]

Problem 7 [[[Problem 7 of Spring 00 Quiz 1 This is the one about red and blue coloring. It has 5 parts. Note that part (c) refers to a fact from the previous problem. We can just give them that fact.]]]