Massachusetts Institute of Technology Handout 62 6.042J/18.062J: Mathematics for Computer Science December 8, 1998 Professors Nancy Lynch and Srinivas Devadas

Practice Final

This practice final was the actual final exam from Fall 1998.

Problem 1. [8 points]

Recall the definition of the Fibonacci numbers:

F_{n} = \begin{cases}0 & if n = 0 \\ 1 & if n = 1 \\ F_{n−1} + F_{n−2} & if n > 1 \end{cases}

(a) [2 points] Which Fibonacci numbers are even? (I.e., find a necessary and sufficient condition on n that characterizes when F_{n} is even). State a theorem of the form: F_{n} is even if and only if…

(b) [6 points] Prove that your answer to part (a) is correct.

Problem 2. [10 points]

Consider an n-player tournament for n ≥ 2 in which there is a match between each pair of players. In each match, there is one winner and one loser (no ties allowed). Let P denote the set of players and let W ⊆ P denote the subset of players who won the most games (I.e., x ∈ W if x wins k games and no other player wins more than k games). Let B(x, y) be a predicate which is true if and only if x beats y. (Note: B(x, x) is always false).

(a) [2 points] Express the following statement using quantifiers and logical notation. “For any player x ∈ W and any other player z, either x beats z or there exists a player y such that x beats y and y beats z (or both)”.

(b) [2 points] Write the negation of the preceding statement in logical notation without using the negation or complement symbol. Also, do not use the ≠ symbol for this part. (Note: B(z, x) implies z ≠ x). You do not need to prove your answer is correct.

(c) [6 points] Prove the statement in part (a). (Hint: The simplest proofs do \underline{not} use induction.)

Problem 3. [8 points]

Find a closed form expression for T (n) in each of the following sums and recurrences. In order to save time in calculations, you can express your answer using Θ notation. You do not need to prove your answer. (In each case n ∈ ℕ, but you can ignore the case when n = 0).

(a) [2 points]

T (n) = ∑_{i=1}^{n} \frac{2}{i}

(b) [2 points]

T (n) = ∑_{i=1}^{n}(i + 3)

(c) [2 points]

T (n) = \begin{cases}1 & if n ≤ 4 \\ T (⌊\frac{n}{4}⌋) + T (⌊\frac{n}{3}⌋) + n^{2} & if n > 4 \end{cases}

(d) [2 points]

T (n) = \begin{cases}1 & if n ≤ 4 \\ 2T (⌊\frac{n}{4} + \sqrt{n}⌋) + \sqrt{n} & if n > 4 \end{cases}

Problem 4. [6 points]

Solve the following recurrence for T (n).

T (n + 1) = 6T (n) − 9T (n − 1) + 2^{n}

with the initial conditions T (0) = 1, T (1) = −1.

Problem 5. [10 points]

(a) [5 points] Calculate the number of ways the integers from 1 to 9 can be arranged so that no even integer is in its natural position. (For example 2 is not in the second position, and so on). Specify your answer as an integer or as the sum of products of integers. (You may include factorials in your answer but not binomial coefficients).

(b) [5 points] How many strings are there with n 1’s, 2n 2’s, and 3n 3’s? Leave your answer in the form of a ratio of factorials. You do not need to prove that your answer is correct.

Problem 6. [8 points]

Consider an n-node undirected graph G = (V, E). A simple k-cycle (2 < k ≤ n) in G is a sequence of distinct nodes v_{1}, v_{2}, …, v_{k} for which (v_{1}, v_{2}) ∈ E, (v_{2}, v_{3}) ∈ E, …, (v_{k−1}, v_{k}) ∈ E, and (v_{k}, v_{1}) ∈ E. Note that v_{1}, v_{2}, …, v_{k} is the same cycle as v_{2}, v_{3}, …, v_{k}, v_{1}, and so forth. Also, v_{1}, v_{2}, …, v_{k} is the same cycle as v_{k}, …, v_{2}, v_{1}.

(a) [4 points] What is the maximum possible number of distinct simple k-cycles in G for a given k (assuming all possible edges are present in G)? (Note: for n = 3, k = 3 the answer is 1).

(b) [4 points] Now suppose that G is constructed randomly as follows: For every pair of nodes {v_{i}, v_{j}}, toss a coin of bias p (i.e., the coin is heads with probability p). Include the edge {v_{i}, v_{j}} if the coin comes up heads. Assume that the coin tosses are mutually independent. What is the expected number of simple k-cycles in G ? (If you were not able to solve part (a), you may let X denote the answer to part (a) and express your answer in terms of X, k, and p).

Problem 7. [9 points]

The gambling game Yahtzee is played with five fair, mutually independent six-sided dice. In the following questions, you may leave factorials and binomial coefficients in your answer.

(a) [3 points] A Yahtzee is a throw of the five dice that results in all dice having the same value. Find the probability of a Yahtzee.

(b) [3 points] Find the probability of a straight. A straight is either a throw of {1, 2, 3, 4, 5} or {2, 3, 4, 5, 6}. (Note that the dice are unordered - e.g., any roll which results in one 1, one 2, one 3, one 4, and one 5 counts as a straight).

(c) [3 points] A full house is a result in which there is a group of three dice with the same number, and a group of two dice with the same number (for example {2, 2, 5, 5, 5} is full-house). A Yahtzee doesn’t count as a full house. Find the probability of a full house.

Problem 8. [12 points]

Bobo decides to bet one dollar at a casino. However, he’s not sure what game he wants to play.

• The probability that Bobo plays poker is 20%, in which case he has a 30% chance of winning $2 and a 70% chance of losing $1.

• The probability that Bobo plays blackjack is 20%, in which case he has a 40% chance of winning $1 and a 60% chance of losing $1.

• The probability that Bobo plays the slot machines is 60%, in which case he has a 30% chance of winning $1 and an 70% chance of losing $1.

Let X denote Bobo’s winnings when he makes one bet according to the above probabilities.

(a) [2 points] What is Ex[X]?

(b) [2 points] What is Ex[X^{2}]?

(c) [4 points] What is Var[X]?

(d) [4 points] If we know that Bobo won one dollar at the casino, what is the probability that he played blackjack?

Problem 9. [14 points]

The spider is expecting guests and wants to catch 500 flies for her dinner. The expected number of flies caught in the web per hour is 40.

(a) [4 points] What is an upper bound to the probability that the spider will have caught 500 flies in 10 hours?

(b) [2 points] What is a lower bound to the probability that the spider will have to wait more than 10 hours to catch 500 flies?

(c) [4 points] The spider checks her log and discovers that the standard deviation for the number of flies caught in an hour is 20. Find an upper bound on the probability that the spider will catch 500 flies within 10 hours, using this additional information.

(d) [4 points] The spider discovers additional interesting information. The standard deviation is not 20 after all, but 100 flies pass by her web every hour. 60 of these flies are quite small and are caught with probability 1/6 each. 40 of the flies are big and are caught with probability 3/4 each. Assume all fly interceptions are mutually independent. Using this information, find an upper bound on the probability that the spider will catch 500 flies within 10 hours. (Since you don’t have a calculator, you may leave ln and e in your answer).

Problem 10. [8 points]

Six computers c_{1}, …, c_{6} are connected in a circle so that c_{1} is connected to c_{2} and c_{6}, c_{2} is connected to c_{1} and c_{3} and so forth. There is also a seventh computer c_{0} with direct connections to the other six computers. When two computers want to communicate the signal is transmitted through the shortest path on the network. Ties are resolved in favor of the path that does not pass through c_{0}. During each second of time, each computer sends one signal. Each signal is sent to a randomly selected computer (the source and destination of any signal are always different). All random selections are drawn from the uniform distribution, but there may be dependencies.

(a) [2 points] Draw the graph of the network.

(b) [6 points] For each edge, calculate the expected traffic per second through the edge. Edges are bidirectional so a signal passing through the edge in either direction counts as traffic through the edge.

Problem 11. [7 points]

A job queue is operating under the following assumptions:

1. At the start of each minute (begining at time zero), a job is removed from the queue for processing (if the queue is nonempty). This job is processed during the ensuing 60 seconds.

2. During the course of each minute (in between the times when jobs are removed from the queue), new jobs can arrive in the queue. The probability that one new job arrives is 1/2. The probability that two new jobs arrive is 1/4. The probability that no new jobs arrive is 1/4. The number of job arrivals at each step are mutually independent.

3. The queue overflows if it ever has 10 or more jobs.

Let R be the minute during which the queue first overflows. (If there are 10 or more jobs in the queue before we start, then R = 0).

Let J_{n} = Ex[R|n jobs in the spooler before we start]. Set up a recurrence for J_{n}. State special cases and initial conditions. Do NOT solve the recurrence