Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science April 15, 1999 Professor Albert R. Meyer

Conflict Quiz 2

Your Name:

Circle the name of your TA:

Matt Blum  Stas Jarecki&Eric Lehman Amit Khetan
Mike Leonida Zulfi Ramzan  Jared Smith-Mickelson

• This quiz is closed book, except for a one-page sheet of notes you have prepared. No calculators either.

• There are six (6) problems totaling 100 points. Problem parts are labelled with their point values.

• Put your name on the top of every page — these pages will 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.

• GOOD LUCK!

DO NOT WRITE BELOW THIS LINE

Problem Points  Grade  Grader
1  16
2  20
3  18
4  15
5  13
6  18
Total  100

Handout ??: Conflict Quiz 2  2  Name:

Problem 1. [16 pts] Divide and Conquer.

The easily-applied version of the Master Theorem for Divide and Conquer recurrences given in tutorial is stated below. In the indicated space next to each of the following recurrences, write an “X” if this Master Theorem does not directly apply to it. If it does directly apply, then write the Θ() bound given by the Theorem for this recurrence.

T (n) = 3T (⌈n/2⌉) + n^{log_{2} 3}

T (n) = T (n) − n^{2}

T (n) = 3T (⌈n/2⌉) + n log_{2} n

T (n) = 3T (n − 1) + 2T (n − 2)

T (n) = 3T (⌈n/2⌉) + n^{log_{2} 3} log_{2} n

T (n) = \frac{1}{2}T (⌈n/2⌉) + 1/\sqrt{n}

T (n) = 2T (⌈n/2⌉) + n^{log_{2} 3}

T (n) = T (⌈n/5⌉) + T (⌈3n/4⌉) + 11

Theorem (Divide-And-Conquer Master Theorem). Suppose

T (n) = aT (⌈n/b⌉) + f(n)

where T, f : ℕ → ℝ, a > 0, and b > 1. Let β ::= log_{b} a. Then

T (n) = \{ \begin{matrix}Θ(n^{β}) & if f(n) = O(n^{α}) for some α < β, \\ Θ(n^{β} log n) & if f(n) = Θ(n^{β}), \\ Θ(n^{α}) & if f(n) = Θ(n^{α}) for some α > β. \end{matrix}

Problem 2. [20 pts] Linear Recurrences. Solve the linear recurrence

T (n) = 3T (n − 1) − 4T (n − 3) + 6

subject to the initial conditions T (0) = 11, T (1) = 6, T (2) = 28.

Problem 3. [18 pts] Bijections.

(a) [4 pts] Give an example of an infinite set, A, such that there is no injection from A into the set, ℝ, of real numbers.

(b) [4 pts] Give an example of an infinite set, A, such that there is no injection from ℝ into A.

(c) [10 pts] Prove that the set of all finite sequences of integers is countable.

Problem 4. [15 pts] Inclusion-exclusion. There are 130 students in 6.042. Some students are blessed with one or more of the qualities of being healthy, wealthy, and/or lucky. A few students are cursed by the lack of all these qualities. Moreover,

1. every student that is both healthy and wealthy is also lucky,

2. half of the lucky students are healthy,

3. half of the lucky students are wealthy,

4. seventy (70) students are healthy, and

5. thirty (30) students are wealthy. Exactly how many cursed students are there in 6.042?

Problem 5. [13 pts] Permutations and Combinations.

k\binom{n}{k} = n\binom{n − 1}{k − 1}

(a) [4 pts] Prove this equation algebraically.

(b) [9 pts] Now give a combinatorial argument proving this equation. That is, describe two different procedures for counting the same things, where the lefthand side of the equation clearly describes the number of outcomes of the first procedure and the righthand side the number of outcomes of the second procedure.

Problem 6. [18 pts] Stars and Bars. The king positioning in an arrangement of a deck of 52 playing cards is the sequence of numerical positions in the deck, from one to 52, of the four successive kings. For example, the king positioning (1, 2, 3, 4) means all the kings come at the beginning of the deck. The king positioning (1, 18, 35, 52) describes the situation in which the kings are spaced uniformly—with exactly 16 cards between successive kings.

Your answer to each of the following questions may be an arithmetic expression involving factorials and/or multinomial coefficients.

(a) [4 pts] How many king positionings are there?

(b) [8 pts] How many king positionings are there in which no two kings are adjacent?

(c) [6 pts] Of the 52! possible arrangements of the deck, how many have no two kings adjacent?