6.042 Final Exam

Fall 2000

Problem 1 [33 points] Miscellaneous Grading: for parts a, c, d, e, give 2 points for each number correctly circled or correctly left uncircled. For part b, give 1 point for each number.

(a) (6 points) Circle the numbers of ALL of the following which are logical tautologies: 1, 3.

(b) (3 points) Define the relation R such that nRm whenever n and m are natural numbers such that |n − m| is the square of a natural number (remember that 0 is a natural number). Circle the numbers of ALL of the following which apply to R: 1, 2.

(c) (10 points) Circle the numbers of ALL of the following statements that are true for all m, n > 0 ∈ N. Let G be an m by n grid graph. 2, 3.

(d) (8 points) Circle the numbers of ALL of the following functions which are θ(n): 1, 4.

(e) (6 points) Circle the numbers of ALL of the following which are uncountably infinite sets: 2, 3.

Problem 2 [16 points] Counting Connected Components of a Graph

(a) (3 points) If H is the graph given below, and the edge (v, w) is the one selected in step 2.1, draw the graph H after step 2.4 in the algorithm. Label the z vertex in your graph.

Grading: 1 point for leaving edges not between v or w and some vertex in the graph. 1 point for correctly determining which edges to z belong there. .5 points for labelling z .5 points for removing v and w and their incident edges.

(b) (3 points) Model this algorithm as a state machine.

Grading: 1 point for having H in the states. .5 points for correct start state. 1 point for correct transitions. .5 points for having no transitions when there are no edges.

(c) (7 points) Prove, using an invariant, that if the algorithm terminates, the output is the number of connected components of G. You may assume that in a graph with no edges, the number of connected components is equal to the number of vertices.

Grading: 1.5 points for formulating an invariant which is sufficient to show correctness. 4 points for proving the invariant (use normal proof standards). 1.5 points for using the invariant to prove correctness (use normal proof standards).

(d) (3 points) Prove that this algorithm always terminates.

Grading: 1 point for coming up with a termination function. 1 point for proving it is decreasing. 1 point for proving it is always a nonnegative integer.

Problem 3 [9 points] Lines That Cross and Lines That Don’t

Suppose we have a set L of 26 different lines with equations in the form y = mx + b for real m and b. Prove that there is either

1. A set S of 6 lines that never intersect one another when x > 0, or

2. A set T of 6 lines such that any two of them intersect one another at some point where x > 0.

Hint: Use Dilworth’s Theorem.

Grading: 9 points for the proof, using normal proof standards, if they DON’T use Dilworth’s theorem. If they do use Dilworths: 3 points for coming up with a partial ordering which is sufficient. 1 point if they don’t have a sufficient partial ordering but they do have SOME partial ordering on the lines. 1 point for proving their relation is a partial order. 1 point for finding the value of t that works with Dilworth’s Theorem. 2 points for proving one of the sets exists if there is a chain 2 points for proving the other set exists if there is an antichain Problem 4 [10 points] Recurrence Relations

(a) (5 points)

A_{n} = 1 + n(−1)^{n}.

Grading: 1 point for identifying the characteristic polynomial. 1 point for factoring the characteristic polynomial. 2 points for giving the general form c_{1}1^{n} + c_{2}(−1)^{n} + c_{3}n(−1)^{n} 1 point for solving correctly for c_{1}, c_{2}, and c_{3}. Give full credit if they get the right answer from some other method.

(b) (5 points)

A_{n} = (−1)^{n} + n

.

Grading: 1 point for giving the general form of the homogenous part. 1 point for guessing a particular solution whose FORM is correct. (ie, an + b or an^{2} + bn + c. 2 points for correctly solving for the coefficients in their particular solution. 1 point for correctly solving for c_{1}, c_{2}, and c_{3} given their particular solution.

Problem 5 [6 points] Summations

(a) (2 points) Find a closed form for

∑_{i=0}^{∞} ∑_{j=1}^{n} \frac{1}{2^{i}}

Solution: 2n.

Grading: 1 point for the inner sum (it does not depend on j). 1 point for the geometric sum.

(b) (4 points) Find a closed form for

∑_{i=0}^{n}(i + 1)x^{i}.

Solution:

\frac{(n + 1)x^{n+2} − (n + 2)x^{n+1} + 1}{(x − 1)^{2}}

Grading: If they did the differential method: 1 point for getting the upper limit right on ∑^{n+1} x^{i} 1 point for finding the closed form of this 1 point for differentiating correctly 1 point for simplifying their answer.

If they looked up solutions: 1 point for splitting up the sum into ∑_{i=0}^{n} x^{i} + ∑_{i=0}^{n} ix^{i} 1 point for giving the closed form of each part (by lookup) 2 points for simplifying their answer. Yeah, 2 points is a lot but if the do it this way it’s the only thing they have to WORK at.

If they did it some other way: 3 points if they give a correct but unsimplified answer. 4 points if they give a correct, simplified answer.

Problem 6 [10 points] Combinatorics Let S be the set {a, b, c, d, e} and let T be the set {1, 2, 3, 4}. (2 points each) Grading: 2 points for a correct answer. 1.5 points for an answer that would be correct but was simplified incorrectly. 1 point for some gross unsimplified mess that might be correct. .5 points for an incorrect answer that shows understanding.

(a) What is the number of binary relations from S to T? Solution: 2^{20} = 1048576

(b) What is the number of functions from T to S? Solution: 5^{4} = 3125

(c) What is the number of injective functions from T to S? Solution: 5! = 120

(d) What is the number of surjective functions from T to S? Solution: 0

(e) What is the number of surjective functions from S to T? Solution: 2 · 5! = 240 Problem 7 [16 points] Coloring Grid Graphs, Yet Again Parts (a) - (d): grading: 2 points for a correct answer. 1 point for an incorrect answer that shows understanding.

(a) (2 points) What is Pr(A)? Solution: 1/4

(b) (2 points) What is Pr(B|A)? Solution: 1/3

(c) (2 points) What is Pr(A|C)? Solution: 1/4

(d) (2 points) What is Pr(B|A ∩ C)? Solution: 1/3

(e) (4 points) Which pairs of the events A, B, and C are independent? Solution: (A, C) and (B, C) are independent, (A, B) is not. Grading: 1.5 points for saying that A and C are independent. 1.5 points for saying that B and C are independent. 1 point for NOT saying that A and B are independent.

(f) (4 points) What is Ex(X)? Solution: 48 Grading: 2 points for setting up variables for each vertex which have simple expectations to calculate. 1 point for correctly expressing X as the sum of these variables. 1 point getting the correct expectation for expectation for each variable. 4 points for having the correct answer, even if they don’t do the problem this way.

Problem 8 [20 points] The Florida Election

(a) (2 points) Let X be a random variable that represents the number of votes Gore gets in this county. What is the expected value of X?

Solution: 6000.

Grading: No credit for a wrong answer.

(b) (3 points) What is the variance of X?

Solution: 2400.

Grading: 3 points for a correct answer. 1 point for having the formula V (X) = np(1 − p) for n independent Bernoulli trials, but using it incorrectly. .5 points for giving the equation V (X) = E(X^{2}) − E(X)^{2} and not being able to come up with the answer.

(c) (5 points)

Solution: Pr(...) ¡ 20/21.

Grading: 2 points for having Markov’s inequality stated correctly. 1 point for substituting E(X) correctly. 1 point for having t correct. 1 point for having the inequality in the right direction.

(d) (5 points)

Solution: (two-sided formula): Pr(...) ¡ 2/75 = 2400/90000

(one-sided formula): Pr(...) ¡ 2/77 = 2400/92400

Either formula is acceptable.

Grading: 2 points for having Chebyshev’s inequality stated correctly. .5 points for having E(X) correct. 1 point for having V (X) correct. 1 point for having the correct value of t. .5 points if they use the two-sided formula, for saying that Pr(X − E(X) ≥ t) ≤Pr(|X − E(X)| ≥ t).

(e) (5 points)

Solution: Pr(X ≥ (21/20)E(X)) ≤ e^{−(ln(21/20)+(20/21)−1)(21/20)(6000)} = \frac{e^{300}}{(21/20)^{6300}} ≈ e^{−7.37803} ≈ .000625

Grading: 2 points for having Chrenoff’s inequality stated correctly. .5 points for having E(X) correct. .5 points for having c correct. .5 points for having α correct. .5 points for plugging in the values to get either of the approximate answers above.

Problem 9 [6 points] MIT Football Grading: Give credit for any answers that work, not just our solution.

(a) (2 points). Theorem 2 If the numbers on the jerseys are integers in the set {1, …, 100} then the difference between the numbers on some pair of jerseys is a multiple of 31. Pigeons: Jerseys Pigeonholes: \underline{Numbers \{0, 1, …, 31\}} Pigeon p is in hole h if: \underline{p ≡ h mod 32} Grading: 1 point per line.

(b) (4 points). Theorem 3 If the numbers on the jerseys are integers in the set {1, …, 100} then if the jerseys are lined up in ascending order by their numbers, there is a nonempty consecutive subset of the jerseys whose numbers add up to a multiple of 32. Pigeons: \underline{Sum of the first i jerseys} Pigeonholes: \underline{Numbers \{0, 1, …, 31\}} Pigeon p is in hole h if: \underline{p ≡ h mod 32} Grading: 2 points for the Pigeons, 1 point each for the other two lines.

Problem 10 [6 points] Die Rolling

Say you roll a fair 6-sided die. If you get a 6, you may roll again, and add 6 to the outcome; if you roll multiple 6’s in a row, you continue to roll again. So, for example, if you roll a 6 and then a 5, the outcome is 11; if you roll a 6, then a 6, then a 6, then a 2, the outcome is 20.

What is the expected value of the outcome?

Solution: \frac{21}{5}

Grading: Full points for a correct answer. 4 points for a correct answer in non-closed form. If they do this with Wald’s theorem: 2 points for correctly setting up Q (number of die rolls) and R_{i} (value of each die roll) 1 point for correctly calculating Ex(R_{i}) = 7/2 2 points for correctly calculating Ex(Q) = 6/5 1 point for multiplying Ex(R_{i})Ex(Q) to get their answer.

Problem 11 [10 points] Chess Matches

Math Moose and Theory Pig have been playing a series of chess games, and have noticed a number of facts:

• Math Moose wins any given game with probability 8/17.

• If Math Moose wins, he is equally likely to have played either white or black.

• If Math Moose loses, then with probability 8/9, he played black.

• If Math Moose plays white, he always takes Theory Pig’s queen at some point in the game.

• If Math Moose plays black and wins, he takes Theory Pig’s queen with probability 1/2.

• If Math Moose plays black and loses, he takes Theory Pig’s queen with probability 1/4.

(a) (4 points) Define the sample space, and give the probability associated with each outcome.

Solution: Math Moose plays white, wins, and takes Theory Pig’s queen: 4/17 Math Moose plays white, loses, and takes Theory Pig’s queen: 2/17 Math Moose plays white, loses, and doesn’t take the queen: 2/17 Plays black, wins, and takes: 1/17 Plays black, loses, and takes: 2/17 Plays black, loses, and doesn’t take: 6/17

Grading: 4 points if they get all these cases with correct probabilities If they draw a tree: 2 points for drawing the tree with the decisions in the right order (white/black, then win/loss, then take/don’t take). .5 points for getting the probabilities right at each of the three levels. .5 points for multiplying to get the probability for each case. If they draw a Venn Diagram: .5 points for each of the eight regions (including the two regions which are empty)

(b) (3 points) What is the probability that Math Moose wins a random game in which he plays white?

Solution: 4/5.

Grading: 3 points for answering 4/5. 1 point for answering 4/17 (the probability he wins and plays white)

(c) (3 points) What is the probability that Math Moose wins a random game, given that he takes Theory Pig’s queen?

Solution: 5/9.

Grading: 3 points for answering 5/9. 1 point for answering 5/17.

Problem 12 [8 points] Overloading Circuits

(a) (5 points) Express the expected number of memory cells that burn out in a power surge, in terms of p. (Hint: use linearity of expectation.)

Solution: \frac{1}{1−p}.

Grading: If they use the linearity of expectation method: 1 point for expressing the desired variable X in terms of the sum of indicator variables. 2 points for determining the probability of the indicator variables being 1. 2 points for summing the probabilities. The answer need NOT be in closed form; if it’s not it’ll bite them in the butt on part (b). If they use some other method: 3 points for having some formula for expectation which is true (ie Ex(X) = ∑_{s∈S} sPr(X = s)) 2 points for plugging in the right things.

(b) (3 points) It is discovered that the mean number of memory cells that burn out from a power surge is 10. What is p?

Solution: 9/10.

Grading: 3 points if they get 9/10. 1 point if their answer for part (a) was incorrect but they solved for p correctly.