Massachusetts Institute of Technology Handout 52 6.042J/18.062J: Mathematics for Computer Science May 7, 2000 Professors David Karger and Nancy Lynch

Practice Final Quiz (Fall ’99)

Problem 1 [18 points] Injections and Cardinality.

(a) [8 points] Let f : D → D be a function from some nonempty set D to itself. In the following propositions, x and y are variables ranging over D, and g is a variable ranging over functions from D to D. Circle all of the propositions that are equivalent to the proposition that f is an injection:

a) x = y ∨ f(x) ≠ f(y)

b) x = y ⟹ f(x) = f(y)

c) x ≠ y ⟹ f(x) ≠ f(y)

d) f(x) = f(y) ⟹ x = y

e) ¬[∃x∃y(x ≠ y ∧ f(x) = f(y))

f) ¬[∃z∀x(f(x) ≠ z)

g) ∃g∀x(g(f(x)) = x)

h) ∃g∀x(f(g(x)) = x)

We have proved that the infinite set of real numbers is “strictly bigger” than the infinite set of integers, and the set of integers is “strictly bigger” than any finite set.

(b) [5 points] State precisely what it means to say a set A is “strictly bigger” than another set B.

(c) [5 points] Give an example of a set that is strictly bigger than the set of real numbers.

Problem 2 [13 points] Modular Arithmetic.

(a) [5 points] Prove that there is no x such that 117 · x ≡ 1 (mod 213).

(b) [8 points] Find an integer x for which 123 · x ≡ 1 (mod 2347)

Handout 52: Practice Final Quiz (Fall ’99)  1  Name:

Problem 3 [10 points] Invariants.

(a) Give the definition of a state invariant of a state machine.

(b) Besides the identically false and the identically true state invariants, how many other logically distinct state invariants does the following machine have? Describe them. (Two invariants are logically distinct if there exists a state in which one holds and the other doesn’t.)

State Machine Description: States Q::= {A, B, C, D, E, F, G, H}, transitions:

{(A, B), (B, C), (C, A), (D, E), (E, F)(F, D), (C, D), (G, A), (B, H)} .

Problem 4 [10 points] Stars and Bars.

A juggler plans to juggle 11 rings for his finale. In his bag are 20 identical red rings, 30 identical blue rings, and 40 identical white rings. He must select at least one of each color to be patriotic. An example of a patriotic choice of 11 rings would be: 3 red, 2 white, and 6 blue. How many different patriotic choices are there for the 11 rings?

Problem 5 [10 points] Equivalence Relations and Random Variables.

Define a binary relation ρ on real-valued random variables X, Y by the rule that X ρ Y iff Pr {X ≠ Y } = 0. Prove that ρ is an equivalence relation.

Problem 6 [13 points] Counting with Repetition.

(a) [5 points] How many distinguishable ways are there to rearrange the letters in

“INSTRUCTOR”?

(b) [8 points] … with all vowels consecutive?

Problem 7 [10 points] Conditional Probability.

Boston is justly famous for its enthusiastic sports fans. Surveys show that 90% of adult Bostonians are Celtics fans, and 75% are Red Sox fans. However, only 80% of the Celtics fans are also Red Sox fans. Now suppose that an adult Bostonian is chosen at random from among those that are not Celtics fans. What is the probability that such a person is a Red Sox fan?

Problem 8 [10 points] Markov Bound.

A herd of 350 cows is stricken by an outbreak of ”mad cow” disease. The disease lowers the normal body temperature of a cow, and a cow will die if its temperature goes below 90 degrees F. The disease epidemic is so intense that it lowered the average temperature of the herd to 45 degrees. Body temperatures as low as 20 degrees, but no lower, were actually found in the herd.

(a) [6 points] State a best possible upper bound on the number of cows whose temperature is high enough to survive.

(b) [4 points] Give an example set of temperatures that achieve your bound.

Problem 9 [15 points] Linear Recurrence. You just moved into your new house and you are throwing a housewarming party. You invite 5 people on the first day and tell them to invite their friends. Each newly invited person invites 2 people the day after they are invited.

(a) [5 points] Give a recurrence describing the total number of people invited up to and including the nth day, that is, the people you invited, and the people invited by the people you invited, etc. For example, on the first day, 5 people are invited, by the second day 15 people have been invited—the 5 people invited on the first day and the ten people they invite on the second day—and by the third day, 35 = 15 + 2 · 10 people have been invited.

(b) [5 points] Describe initial conditions for the recurrence.

(c) [5 points] Give a closed form expression equal to the number of people invited by the nth day.

Problem 10 [11 points] Binomial Identity. Suppose you want to choose a team of m people from a pool of n people for your startup company, and from these m people you want to choose k to be the team managers. Prove that you can do this in

\binom{n}{k}\binom{n − k}{m − k}

ways.

Problem 11 [15 points] Trees and Structural Induction.

A full binary tree with its vertices and leaves is defined inductively as follows:

• A simple graph with one vertex is a full binary tree. The vertex is called the root of the tree. The set of leaves of the tree is the set whose sole member is the root. The set of vertices of this tree is the same as the set of leaves.

• If B_{1} and B_{2} are full binary trees such that the vertices of B_{1} and B_{2} are disjoint, then a simple graph consisting of a new vertex with edges from the new vertex to the roots of B_{1} and B_{2} is also a full binary tree, B. The root of B is the new vertex. The vertices of B are exactly its root, the vertices of B_{1}, and the vertices of B_{2}. The leaves of B are exactly the leaves of B_{1} and the leaves of B_{2}.

For example, a full binary tree with 5 nodes and 3 leafs is is shown in Figure INSERT FIGURE.

Prove that for all full binary trees B,

|leaves(B)| = \frac{|vertices(B)| + 1}{2}.

Problem 12 [20 points] Chebyshev Bound.

A man has a pocketful of n keys, exactly one of which will open the door to his apartment. He picks a random key from his pocket, tries to open the door with it, and puts it back in his pocket if it doesn’t work (no, he isn’t very together about key management, and he may try the same key over and over again). He continues trying until he finds the key that works.

(a) [5 points] What is the expected number of trials of keys the man makes until he finds the right one? Hint: Mean time to failure.

(b) [10 points] What is the variance for the number of trials, T, of keys till he finds the right one ? Hint: Some relevant summation formulas are in the Appendix.

(c) [5 points] What is the Chebyshev upper bound on the probability that the man will make at least a 100 trials till success? Let V denote the variance that you were asked to calculate in the previous part, and express your answer as a closed formula using V.

Problem 13 [30 points] Random Graphs.

A simple graph with 10 vertices is constructed by randomly placing an edge between every two vertices with probability p. These random edge placements are performed independently.

(a) [2 points] What is the probability that a given vertex, v, of the graph has degree two?

(b) [5 points] What is the expected number of nodes with degree two?

(c) [15 points] What is the expected number of cliques of size k, that is, subgraphs isomorphic to the complete graph with k vertices? Express your answer as a closed form formula involving binomial coefficients.

(d) [8 points] The previous result implies an interesting fact which you may assume without proof: if p = 1/2, then the expected number of cliques of size 2 log n is greater than one, where n is the total number of vertices in the graph. (In the previous parts we had n = 10; now n is arbitrary.) Oddly, even though we can expect there to be such a clique, no procedure is known to find some clique of size 2 log n in the graph—when there is one—which is much more efficient than exhaustively searching through all possible subsets of vertices of size 2 log n and checking each subset to see if it is a clique. Circle each of the following expressions which correctly bounds the number of subsets such an exhaustive search would examine:

a) O(2^{n})

b) O(n^{2})

c) O(n^{log n})

d) O(n^{2 log n})

Problem 14 [15 points] Probabilistic Prediction.

We have three coins to flip: one has probability 3/4 of coming up heads, another has probability 7/8 of coming up heads, and finally there is one with probability 15/16 of coming up heads. One of the three coins is picked, and this coin is repeatedly tossed.

Explain a way to determine a number of tosses sufficient to allow identification with 99% confidence of the coin being tossed. You do not have to carry out the calculation, and you may cite without proof any of the results from the Appendix or other course material.