Massachusetts Institute of Technology Quiz 2 6.042J/18.062J: Mathematics for Computer Science April 12 2000 Professors David Karger and Nancy Lynch

Quiz 2

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.

• 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, but you must explicitly cite which results you are using and how you are using them.

• 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  20
3  10
4  10
5  10
6  10
7  10
8  10
9  10
Total  100

6.042J/18.062J Quiz 2  2  Name:

Problem 1 [10 points]

(a) [5 points] n > 1 people attend a party. Prove that there must be two people who shake the same number of hands, assuming no one can shake his own hand.

(b) [5 points] Consider a set S of 10 natural numbers chosen from the range 1, …, 50. Prove that there must be two distinct subsets of S that sum to the same value.

Problem 2 [20 points] Counting

For the problems below, you may leave products and binomial coefficients in your final answer.

(a) [5 points] In poker, a flush is a set of five cards, all of the same suit. How many distinct flushes are there?

(b) [5 points] In poker, a straight is a set of cards that, when the suits are ignored, form a five-in-a-row sequence, for example 5, 6, 7, 8, 9 or 8, 9, 10, J, Q. An ace can start a straight (A, 2, 3, 4, 5) or end it (10, J, Q, K, A) but cannot wrap around (no Q, K, A, 2, 3). How many distinct straights are there?

(c) [5 points] A straight flush is a hand that is both a straight and a flush: 5 cards in a row, all the same suit. How many are there?

(d) [5 points] How many 5-card hands are there containing a straight or a flush?

6.042J/18.062J Quiz 2  5  Name:

Problem 3 [10 points] Counting Consider placing n distinguishable books on r distinguishable shelves.

(a) [5 points] If the order of books on each shelf doesn’t matter, how many distinct placements are there?

(b) [5 points] If order on the shelf matters, how many distinct placements are there?

Problem 4 [10 points] Order of Growth

(a) [5 points] From lecture, we know that any comparison-based sorting algorithm 𝔸 must take time Ω(n log n) on n elements. Which of the following is a consequence of this fact? Explain your answer.

a) There is some constant c > 0 for which all executions of 𝔸 will perform exactly cn log n steps.

b) There is some constant c > 0 for which all executions of 𝔸 will perform at least cn log n steps.

c) There is some constant c > 0 for which the longest executions of 𝔸 will perform at least cn log n steps.

d) There is some constant c > 0 for which all executions of 𝔸 will perform at most cn log n steps.

e) There is some constant c > 0 for which the longest executions of 𝔸 will perform at most cn log n steps.

(b) [5 points] Prove that 10n^{2} = O(n^{3}).

6.042J/18.062J Quiz 2  7  Name:

Problem 5 [10 points] Summations

(a) [5 points] Express the following in closed form

∑_{p=1}^{∞} ∑_{q=p}^{∞} x^{p}y^{q}.

(Note that the lower indices are not constants.)

(b) [5 points] Prove tight asymptotic bounds on

∑_{n=1}^{m} \frac{1}{n ln n}.

Hint: consider \frac{d}{dx} ln ln x.

6.042J/18.062J Quiz 2  9  Name:

Problem 6 [10 points] Binomial Coefficients Prove that

∑_{k=1}^{n}k ( \begin{matrix}n \\ k \end{matrix} ) = n2^{n−1}

(a) [5 points] using a combinatorial argument. Hint: choose a committee and a leader.

(b) [5 points] by finding a closed form for ∑_{k=1}^{n} ( \begin{matrix}n \\ k \end{matrix} ) kx^{k} and evaluating it at x = 1.

Problem 7 [10 points] Recurrences

Consider the following recurrence to which the master theorem does not apply:

T (n) = 2T (n/2) + n log_{2} n

(a) [3 points] Perform two iterations of plug-and-chug to reveal a pattern for this recurrence.

(b) [7 points] Prove tight asymptotic bounds for this recurrence. You may assume n is a power of two if it is convenient.

Problem 8 [10 points] Recurrences

The Millicent computer virus has been spreading on computers around MIT. Once a copy of Millicent enters a computer, it is copied to two new (uninfected) computers after one day, then to 3 new computers the second day, and then detected and removed on the third day. Millicent’s creator installed Millicent on 2 computers on day 0 and 2 additional computers on day 1.

(a) [3 points] Due to a tip from inside the FBI that Millicent might be of extraterrestrial origin, Frohike and Langley have been investigating the growth of the Millicent virus; however, they’ve gotten stuck. Help them by stating a recurrence describing the number of computers newly infected on day n for n > 1.

(b) [4 points] Find a closed form for the recurrence you stated in the previous part.

(c) [3 points] Fearing the efforts of the mighty Frohike and suave Langley, Millicent’s creator became frightened and decided to start installing the virus on 5 new computers every day after day 1. State a recurrence for the revised problem and find a closed form solution for the number of computers newly infected on day n.

Problem 9 [10 points] Countability

(a) [5 points] A function f from the natural numbers to the natural numbers is strictly increasing if f(n + 1) > f(n) for every n. Prove that the set of such strictly increasing functions is uncountable.

(b) [5 points] A function f from the natural numbers to the natural numbers is strictly decreasing if f(n + 1) < f(n) for every n. Prove that the set of such strictly decreasing functions is uncountable. Hint: first figure out how to prove that the set of strictly decreasing functions for which f(0) = 1 is countable.