Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science March 15 2000 Professors David Karger and Nancy Lynch

Quiz 1 Solutions

Your Name:

Circle the name of your Tutorial Instructor:

Carl  David  Josh  Ken
Kyle  Robert  Shishir  Victor

Write the hour at which your Friday recitation begins

• This quiz is open book/notes.

• There are 11 pages with 7 problems totaling 70 points. Problem parts are labeled 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 presented in class or in the lecture notes.

• 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!

DO NOT WRITE BELOW THIS LINE

Problem Points  Grade  Grader
1  10
2  10
3  10
4  10
5  10
6  5
7  15
Total  70

Handout ??: Quiz 1 Solutions  2  Name:

Problem 1 [10 points] Quantifiers Consider the following predicates where the universe of discourse is the set of all people: 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 point] No hackers are willing to waltz.

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

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

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

Handout ??: Quiz 1 Solutions  3  Name:

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

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

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

Handout ??: Quiz 1 Solutions  4  Name:

Problem 2 [10 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. (Sketch)

\frac{1}{4}(n + 1)n(n − 1)(n − 2) − \frac{1}{4}n(n − 1)(n − 2)(n − 3) = \frac{1}{4}n(n − 1)(n − 2)[(n + 1) − (n − 3)]
= n(n − 1)(n − 2)

Problem 3 [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 definition of S_{n}.

(a) [1 point] 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) to give the elements of S_{n}.

\begin{matrix}S_{1} & \{0, 1/2, 1\} \\ S_{2} & \{0, 1/4, 1/2, 3/4, 1\} \\ S_{3} & \{0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1\} \end{matrix}

S_{n} contains 2^{n} + 1 elements (including 0 and 1) evenly spaced along the unit interval; i.e., S_{n} = {i/2^{n}|0 ≤ i ≤ 2^{n}}.

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

Strengthen the theorem to

P (n) = “For all a/b ∈ S_{n} with a, b ∈ ℕ where a/b is in reduced form, b = 2^{k} for some k”

Clearly, if ∀n P (n), then ∀n 1/3 ∉ S_{n}. Thus, we need only prove ∀n P (n).

Base cases. 0 = 0/2^{0}, 1 = 1/2^{0}.

Induction. Assume P (n). By the construction of S_{n+1}, all elements of S_{n+1} are of the form (x + y)/2 for some x, y ∈ S_{n}. Fix any two such elements x, y ∈ S_{n}, where (by the induction hypothesis) x = a/2^{k} and y = c/2^{ℓ} with a, b, k, ℓ ∈ ℕ.

Assume WLOG k ≥ ℓ. Then,

(x + y)/2 = (a/2^{k} + c/2^{ℓ})/2
= (a/2^{k} + c2^{k−ℓ}/2^{k})/2
= (a + c2^{k−ℓ})/2^{k+1}

While this may not be in reduced form, reduction cannot introduce any non-2 factors into the denominator, so this fits the form specified by the theorem. Therefore, P (n + 1).

By induction, ∀n P (n). Thus, ∀n 1/3 ∉ S_{n}.

Problem 4 [10 points] Relations

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

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

(c) [2 points] 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 aT^{−1}b)?

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

(e) [3 points] Is the relation “xRy iff x = y or x is not y’s roommate” an equivalence relation? Why or why not?

Problem 5 [10 points] Precedence Relations

Death is planning the end of the world. This involves a number of tasks each of which takes one minute to complete. The prerequisites associated with these tasks are listed below.

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) [5 points] Represent the tasks and their prerequisites as a directed graph.

(b) [5 points] Death is omnipotent and can therefore work on as many tasks at a time as he wishes. What is the minimum amount of time required for him to end the world? Why? (An explanation without proof is fine.)

Problem 6 [5 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 walk connecting a colored node to an uncolored node must include a colored node adjacent to an uncolored node.

Consider the path p = v_{1}v_{2} ⋯ v_{k}, of which v_{1} is colored and v_{k} is uncolored. Assume there is no edge (v_{i}, v_{i+1}) such that v_{i} is colored and v_{i+1} is uncolored. Then, by induction starting from v_{1}, v_{i} are colored for all i, so v_{k} is colored; this is a contradiction.

Problem 7 [15 points] Algorithms

Let G = (V, E) be a simple, undirected graph. The following algorithm, RedBlue, manipulates partial colorings of G using C = {red, blue}. (Partial colorings are defined in 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) [3 points] Formalize this algorithm as a state machine; that is, define Q, Q_{0}, and δ.

A state q consists of a (total) function f from V to {red, blue, uncolored}. A start state is any state in which f maps exactly one v ∈ V to red, and all others to uncolored. The transitions are all of the form:

(q, q′) ∈ δ ⟺ ∃v ∈ V q.f(v) = uncolored
∧[ (q′.f(v) = red ∧ ∃w f(w) = blue ∧ (v, w) ∈ E)
∨ (q′.f(v) = blue ∧ ∃w q.f(w) = red ∧ (v, w) ∈ E) ]
∧∀w ≠ v q.f(w) = q′.f(w)

(b) [3 points] Prove that the algorithm eventually terminates.

We describe a termination function. Define the value of the termination function to be the number d of uncolored vertices. Each step decreases d, so we can appeal to the Termination Theorem and conclude that the algorithm always terminates. Alternatively, we can expand the proof a bit more: since d starts at n − 1 and is always ≥ 0, it must eventually reach some minimum value (by well-ordering), whereupon the algorithm terminates.

(c) [3 points] Using the fact stated in Problem 6, prove that if G is connected, then all vertices are colored when the algorithm terminates.

Say the algorithm terminates with some vertex uncolored. Since the graph is connected, there is a path from v to some colored vertex w. By the given fact, there must be an edge along this path for which one endpoint x is colored and the other y is uncolored. We can apply one of the two steps above, assigning to y the opposite of x’s color. Thus, the algorithm should not have terminated yet.

(d) [3 points] 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.

The Invariant Theorem requires that we show that the condition is true in all the start states, and that it is preserved by every step.

[[[got here]]]

We need to show that the invariant is preserved from one step to the next, which we do by induction on the number of colored vertices.

P (n) =“After n vertices are colored, all red vertices are in A and all blue vertices are in B.”

Base case. In any start state, there is exactly one red vertex in R—by construction—and no blue vertices. Therefore, P (1).

Induction. Assume P (n). Then, consider an execution in which n + 1 vertices are colored. Consider the vertex i which was colored last. If we uncolor it, we can apply the induction hypothesis and conclude that all red vertices were in R and all blue vertices were in B.

Now we must prove that vertex i is colored correctly. Assume WLOG that vertex i is in B. For i to have been colored, it must have been the case that i was adjacent to a colored vertex; but all vertices adjacent to i are in R (by the definition of bipartite), so i must have been colored blue. This satisfies the invariant theorem, so P (n + 1).

Thus, ∀n P (n), so all red vertices are in R and all blue vertices are in B.

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

We proved the algorithm terminates on connected graphs with all vertices colored. By the invariant above, this means all vertices in R are red and all vertices in B are blue. By the definition of bipartite, there exists no pair of like-colored vertices connected by an edge, so this is a valid 2-coloring.