Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science March 14, 2000 Professors David Karger and Nancy Lynch

Problem Set 6

Due Date: March 28, 2000.

Self-study:

Rosen, Section 1.8, on the growth of functions. Self-study problems: 3,7,9,11,13,15,17,19,23,31

Reading:

Rosen: Sections 5.1, 5.2, 5.3, 4.1, 4.2

6.042 Fall 97 Lecture notes (available from course webpage): Lectures 9–12

Problems:

Problem 1 Determine the flaw in the following reasoning and explain your answer.

(∑_{j=1}^{n} a_{j}) (∑_{k=1}^{n} 1/a_{k}) = ∑_{j=1}^{n} ∑_{k=1}^{n} a_{j}/a_{k} = ∑_{k=1}^{n} ∑_{k=1}^{n} a_{k}/a_{k} = ∑_{k=1}^{n} ∑_{k=1}^{n} 1 = ∑_{k=1}^{n} n = n^{2}

Problem 2 Find a closed-form expression for the summation ∑_{i=1}^{n} i^{2}x^{i}.

Problem 3 Show that ∑_{k=1}^{∞} 1/k^{3/2} is bounded from above by a constant.

Problem 4 In this problem, we will prove that the “average” number of divisors of a number of size about n is “about” ln n. More formally, let t(n) be the number of divisors of the number n, and let

T (n) = \frac{1}{n} ∑_{j=1}^{n} t(j)

be the average number of divisors of all numbers less than or equal to n. Show that T (n) ∼ ln n.

Hint: Let the function f(i, j) = 1 if i is a divisor of j, and 0 otherwise. What do the row and column sums of f(i, j) mean?

Problem 5 Asymptotic notation

For each pair of functions (f(n), g(n)) in the table below, indicate whether the statement at the top of the column is true (e.g., whether f(n) = O(g(n))). Assume k ≥ 1, ϵ > 0, and c > 1 are constants. Your answer should be in the form of a table with “yes” or “no” in each box.

f(n)  g(n) f(n) = O(g(n)) g(n) = O(f(n)) f(n) = Θ(g(n))
log^{k} n  n^{ϵ}
n^{k}  c^{n}
\sqrt{n}  n^{sin n}
2^{n}  2^{n/2}
log(n!) log(n^{n})

Problem 6 Recurrences

Consider a set of record items, each carrying some data and a key and the following definition of a majority key.

Definition. The majority key of a set of m records is a key that occurs more than m/2 times.

For example, 2 is the majority key in a set of 3 records which are tagged, consecutively, by keys 1, 2, and 2. On the other hand, in the set of 4 records tagged by keys 1, 2, 3, and 3, there is no majority key.

Consider the following algorithm for finding the majority key of a set of records: If there is an even number of records, we pair adjacent items up (first with second, third with fourth, etc.) and compare their keys. If they have the same key, we keep one of them, otherwise we throw them both away. We run this algorithm recursively on the resulting set. If there is an odd number of items in our set, we find the majority key of the set containing all but the last item. If there was no majority key then we check if the key of the last record is the majority key by explicitly counting how many times this key appears in the whole set. We continue in this fashion until we either get one record, in which case we check if its key is in fact the majority key — again by counting how many times this key appears in the original set — or we end up with no items, in which case we conclude that there was no majority key.

Handout ??: Problem Set 6 3 (a) Prove that if there is a majority key in the initial set of records then this algorithm terminates with a record item carrying that key. (Hint: Find an invariant that is preserved at every stage. Consider the even and odd cases separately.)

(b) Write down a recurrence for worst-case time this algorithm takes. For this part assume that the size of the working set at every stage is even.

(c) Solve the recurrence you wrote down in part (b) to obtain an asymptotic time bound (Θ) for worst-case running time. (We are interested in the order of growth, not the exact constant.)

(d) Argue that this time bound also holds without the assumption that the working set at each stage is even.

Problem 7 Linear Recurrences Find closed-form solutions to the following linear recurrences.

(a) x_{n} = 5x_{n−1} − 6x_{n−2} (x_{0} = 0, x_{1} = 1)

(b) x_{n} = 5x_{n−1} − 8x_{n−2} + 4x_{n−3} (x_{0} = 1, x_{1} = 2, x_{2} = 3)

(c) (Fibonacci Plus) x_{n} = x_{n−1} + x_{n−2} + 1 (x_{0} = 0, x_{1} = 1)

4 Handout ??: Problem Set 6 Problem 8 Injections, Surjections, and Bijections Let f be a function from A to B, and g a function from B to C. The composition g ∘ f is defined by: g ∘ f(x) = g(f(x)). Determine whether each of the following statements is true or false. If it’s true, prove it. If it’s false, give a counterexample.

(a) If f and g are both injective then g ∘ f is injective.

(b) If f and g are both surjective then g ∘ f is surjective.

(c) If f is surjective and g ∘ f is injective then g is injective.

(d) If g is injective and g ∘ f is surjective then f is surjective.

Handout ??: Problem Set 6 5 Problem 9 Counting Using Functions Determine the cardinality of the following:

(a) The number of binary relations on a set A of n elements.

(b) The number of different digraphs without self-loops for a set V of n vertices.

(c) The number of functions from A to B, where |A| = n and |B| = m.

Problem 10 Pigeonhole Principle

(a) Prove that among every set of 18 integers, there exists a pair with sum or difference divisible by 32.

(b) One of the 6.042 TAs has decided to conduct his next tutorial in the following manner: he will arrange his m students in alphabetical order and hand out tutorial problems to each of the students such that each student ends up with one or more problems. The TA claims that using such an arrangement, there is always a group of (one or more) students that are consecutive in the alphabetical order and collectively receive a number of problems that is a multiple of m.

As an example, consider a 6.042 tutorial with m = 10 students in which the students are arranged in alphabetical order and each of which receives 1, 2, 4, 8, 16, 16, 8, 4, 2, 1 problems. Then, since the fourth, fifth, and sixth students have collectively received 40 problems, the TA’s claim holds.

Prove this claim for all m.