Massachusetts Institute of Technology 6.042J/18.062J, Spring ’06: Mathematics for Computer Science March 1

Prof. Albert R. Meyer revised March 1, 2006, 696 minutes

Problem Set 3

Due: March 13

Reading: Notes for Week4

Problem 1. Let x be a string of characters. In this question, we consider the reverse of a string, which we write r(x). For example, if

x = 10110

then

r(x) = 01101

.

(a) Give a recursive definition of r(x), the reverse of a (/ 3.0 8.0) string.

(b) Use your recursive definition in part (a) to prove that for any two strings, x, y:

r(xy) = r(y)r(x).

Problem 2. Fractals are yet another example of a mathematical object that can be defined recursively. In this problem, we consider the Koch snowflake. Any Koch snowflake can be constructed by the following recursive definition.

• Base Case: An equilateral triangle is a Koch snowflake.

• Recursive case: Let K be a Koch snowflake, and let l be a line segment on the snowflake. Remove the middle third of l, and replace it with two line segments of the same length as is done below:

Figure 1: Recursive case of Koch snowflake construction

The resulting figure is also a Koch snowflake.

Copyright © 2006, Prof. Albert R. Meyer. All rights reserved.

Prove by structural induction that the area inside any Koch snowflake is of the form q\sqrt{3}, where q is a rational number.

Problem 3.

Problem 4.

Problem 5.

Problem 6.

Problem 7. Recall the matching problem with n boys and n girls. We know from the notes that the matching algorithm is boy-optimal. In this problem, we further explore the notion of boy and girl optimal.

(a) Suppose that one boy, Ben Bitdiddle, is completely undesirable – that is, he is at the bottom of the preference list of every girl. Is it possible that Ben ends up matched with his most preferred girl? Prove your claim.

(b) Now, consider the reverse scenario – that some girl is completely undesirable, i.e. at the bottom of the preference list of every boy. Is it possible that she ends up matched with her most preferred boy? Prove your claim.

Problem 8. In the previous problem, we considered the situation that somebody completely undesirable is paired with his or her first choice. In this problem, we explore whether or not everybody can be paired with a slightly undesirable person.

Consider an instance of the matching problem with n boys and n girls. Call a person unlucky if he or she is matched up with one of his or her ⌊\frac{n}{2}⌋ last choices. In this problem, we will prove the following:

Theorem The matching algorithm from class never produces a matching in which every person is unlucky.

Fix an execution of the matching algorithm. Define the variables B_{i}, G_{i}, i ∈ {1, 2, …, n} as follows:

Problem Set 3 3 B_{i} = j if the i-th boy is currently courting the j-th girl on his list G_{i} is the number of boys that the i-th girl has rejected.

(a) Show that ∑_{i=1}^{n} B_{i} − ∑_{i=1}^{n} G_{i} is preserved at each step of the matching algorithm.

(b) Formulate an invariant that you can use to prove the theorem, and show that your invariant is correct.

(c) Use your invariant to prove the theorem.

4 Problem Set 3 Massachusetts Institute of Technology Solutions cover sheet 6.042J/18.062J, Spring ’06: Mathematics for Computer Science March 1 Prof. Albert R. Meyer

Student’s Solutions to Problem Set 3

Your name:

Due date: March 13

Submission date:

Circle your TA: Christos Grant Sonya

Collaboration statement: Circle one of the two choices and provide all pertinent info.

1. I worked alone and only with course materials.

2. I collaborated on this assignment with:

got help from:^{1}

and referred to:^{2}

DO NOT WRITE BELOW THIS LINE

Problem Score

1 2 3 4 5 6 7 8

Total

1People other than course staff.

Copyright © 2006, Prof. Albert R. Meyer. All rights reserved.

2Give citations to texts and material other than the Spring ’06 course materials.