Massachusetts Institute of Technology Quiz 1 6.042J/18.062J: Mathematics for Computer Science March 8 2000 Professors David Karger and Nancy Lynch

Quiz 1

Your Name:

Circle the name of your Tutorial Instructor:

• This quiz is open book. There are XXX problems totaling XXX points. Problem parts are labelled with their point values.

• Put your name on the top of every page — these pages may be separated for grading.

• Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please keep your entire answer to a problem on that problem’s page.

• You may assume any of the results from class or notes in any proofs you give.

• Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. Be neat and write legibly.

• GOOD LUCK!

Write the hour at which your Friday recitation begins

DO NOT WRITE BELOW THIS LINE

Problem Points  Grade  Grader
1  20
2  15
3  20
4  20
5  25
Total  100

6.042J/18.062J Quiz 1, Problem 1  2  Name:

Problem Problem 1 [10 points] Quantifiers Consider the following predicates: P (x): x is a hacker Q(x): x is an MIT student R(x): x is an artist S(x): x is willing to waltz Express each of the following statements using quantifiers, logical connectives, and and the above predicates:

(a) [1 points] No hackers are willing to waltz.

(b) [1 points] No artists are unwilling to waltz.

(c) [1 points] All MIT students are hackers.

(d) [1 points] MIT students are not artists.

(e) [4 points] Does (d) follow logically from (a), (b), and (c)? If so, give a proof. If not, is there a counterexample?

(f) [1 points] Translate into English: (∀x)(R(x) ∨ S(x) ⟹ Q(x)).

(g) [1 points] Translate into English: (∃x)(R(x) ∧ ¬Q(x)) ⟹ (∀x)(P (x) ⟹ S(x).

6.042J/18.062J Quiz 1, Problem 2  3  Name:

Problem Problem 2 [ points] Induction Prove by induction (other methods will not receive credit) that

(1 · 2) + (2 · 3) + (3 · 4) + ⋯ + (n − 1)n = \frac{1}{3}(n − 1) · n · (n + 1)

whenever n is a natural number greater than 1.

6.042J/18.062J Quiz 1, Problem 3  4  Name:

Problem Problem 3 [10 points] Induction The denizens of the land of Frohike worship prime numbers: their currency—the Eebae^{TM}—only uses coins of values 5, 7, and 11 Eebaes. The Frohikies have discovered over time that any value of at least 14 Eebaes can be produced using some combination of these coins, but some values below 14 are not possible. Prove by induction that all values of at least 14 Eebaes can be made from these three coin values.

6.042J/18.062J Quiz 1, Problem 4  5  Name:

Problem Problem 4 [10 points] Structural Induction Consider the sets S_{1}, S_{2}, … defined inductively as

• S_{0} = {0, 1}

• For all n ≥ 1, S_{n} = \{\frac{x+y}{2} | x, y ∈ S_{n−1}\} i.e., where S_{n} contains the average values of each pair of numbers in S_{n−1}. Note we allow x = y in the average.

(a) [1 points] Write out the elements of each of the following sets: S_{1}, S_{2}, and S_{3}.

(b) [2 points] Generalize (in your own words or in symbols) what the elements of S_{n} are.

(c) [7 points] Prove by induction that for all n ∈ ℕ, 1/3 ∉ S_{n}. You may not assume your generalization from the previous part is true; you must prove that statement if you wish to use it.

6.042J/18.062J Quiz 1, Problem 5  6  Name:

Problem Problem 5 [ points] Relations

(a) What is the common name for the reflexive closure of the “less than” relation?

(b) What is the common name for the transitive closure of the “child of” relation?

(c) What is the common name for the inverse of the “teaches relation (that is, if xT y means x teaches y, how do we say xT^{−1}y)?

(d) Consider the partial order “aRb iff a divides b without remainder” on the universe natural numbers greater than 1. What are the minimal elements under this relation usually called?

(e) Let xCy denote “x is a child of y.” What is the common English way to say “(x, y) ∈ C^{−1} ∘C^{−1} ∘C ∘C and x ≠ y”?

(f) Is the relation “xRy iff x = y or x is not y’s roommate” an equivalence relation? Why or why not?

6.042J/18.062J Quiz 1, Problem 6  7  Name:

Problem Problem 6 [ points] Precedence Relations

Death and Destruction are planning the end of the world. This involves a number of tasks (each taking one minute) with particular prerequisites:

Abbrv. Task  Prerequisites
C  Compose a requiem
N  Notify the UN  B
D  Signal the daemons  B
B  Blow the trumpet
T  Sell T-shirts: “All I got was this lousy t-shirt.” N
Q  Grade the 6.042 quiz  S
G  Open the gates  D,N
S  Put out the sun  C,N

(a) Represent the tasks and their prerequisites in a graph.

(b) Death and Destruction are omnipotent and can therefore work on as many tasks at a time as they wish. What, then, is the minimum amount of time required for them to end the world? Why (an explanation without proof is fine)?

Problem Problem 7 [ points] Graphs

Let G = (V, E) be a simple, undirected graph, and let C be a set of colors. Define a partial coloring of G using C to be a function that assigns to each node in V either a color in C or no color. (That is, it colors some, none, or all of the nodes using colors in C.) Define a partly colored graph to be a simple, undirected graph G = (V, E) together with a partial coloring of G.

Prove the following fact about partly colored graphs:

In a partly colored graph, any path connecting a colored node to an uncolored node must contain some edge with one colored endpoint and one uncolored endpoint.

Problem Problem 8 [ points] Algorithms Let G = (V, E) be a simple, undirected graph. The following algorithm, RedBlue manipulates partial colorings of G using C = {red, blue}. (You can find the definition of a partial coloring in the statement of the previous problem.)

Initially, one vertex r of G is colored red, and all the other vertices are uncolored. At each step, one of two events occurs:

a) Some uncolored vertex v that is adjacent to a red vertex becomes blue.

b) Some uncolored vertex v that is adjacent to a blue vertex becomes red.

If neither rule can be applied, the algorithm terminates.

(a) Formalize this algorithm as a state machine; that is, define Q, Q_{0}, and δ.

(b) Prove that the algorithm eventually terminates.

(c) Using the fact stated in the previous problem, prove that if G is connected, then all vertices are colored when the algorithm terminates.

(d) Consider applying this algorithm to bipartite graphs, i.e., graphs in which the vertices can be partitioned into two sets A and B such that there is no edge between any pair of vertices in A, and similarly for B. Suppose the node r that is colored red in the initial state is in set A. Using the Invariant Theorem, prove that in any reachable state, only vertices of A are colored red and only vertices of B are colored blue.

(e) Combine the previous parts to prove that when run on a connected bipartite graph, the above algorithm terminates and outputs a valid 2-coloring.