## Description

Assigned Problems

Exercises (Do not hand in) Chapter 1, Problems 1-3, 5. Chapter 2, Problems 3-5, 7.

Following are the problems to be handed in, 25 points each.

1. (Resident Matching, 2-page limit – your solutions should fit on two sides of 1 page).

The situation is the following. There were m teams at Google, each with a certain number of

available positions for hiring interns. There were n students who want internships at Google this

summer, each interested in joining one of the teams. Each team had a ranking of the students

in order of preference, and each student had a ranking of the teams in order of preference. We

will assume that there were more students who want an internship at Google than there were

slots available in the m teams.

The interest, naturally, was in finding a way of assigning each student to at most one team

at Google, in such a way that all available positions in all teams were filled. (Since we are

assuming a surplus of potential interns, there would be some students who do not get assigned

to any team.) We say that an assignment of students to Google teams is stable if neither of the

following situations arises.

• The first type of instability that can occur is that there is a team t, and there are students

s and s0, so that

– s is matched with t, and

– s0 is assigned to no team, and

– t favors s0 over s.

• The second type of instability that can occur is that there are teams t and t0 and students

s and s0 so that

– s is matched with t, and

– s0 is matched with t0, and

2

– t favors s0 over s, and

– s0 favors t over t0.

So we basically have the Stable Matching Problem, except that, one, teams generally want more

than one intern, and, two, there is a surplus of students who want internships at Google. Show

that there is always a stable assignment of students to Google teams, and give an algorithm to

find one.

Please give a clear description of your algorithm. Don’t forget to prove its correctness and

analyze its time and space complexity.

2. (Time complexity, 2-page limit – your solutions should fit on two sides of 1 page). Part (a)

has 15 points and part (b) has 10 points. The top of your solution for part (a) should have the

functions in order by their letter, with no spaces, commas, etc. between them. (For example,

abc). If you do not include this you will automatically lose 75% of the credit. (Functions that

are equivalent should be in alphabetical order)

(a) Rank the following functions by increasing order of growth, that is, find an arrangement

g1, … of the functions satisfying g1(n) = O(g2(n)), g2(n) = O(g3(n)), …. Break the functions

into equivalence classes so that f and g are in the same class if and only if f(n) = Θ(g(n)).

Note that log(·) is the base 2 logarithm, logb

(·) is the base b logarithm, ln(·) is the natural

logarithm, and logc

(n) denotes (log(n))c

(for example, log2

(n) = log(n) × log(n)).

a. ln(ln n) b. n log n c. 14 log3 n d.

Xn

i=5

(i + 1)

2

e. log2

(n)

f. n2 g.

Xn

i=1

1

2

i

h. log(n!) i. 3

n

j. nlog 7

k.

Xn

i=1

3

i

l. 2

log2

(n) m. 2

log n n. n! o. n

p. 2

log4 n q.

√

n r. log(n

2

) s. 4

log n

t. (

5

4

)

n

(b) For each of the following statements, decide whether it is always true, never true, or sometimes true for asymptotically nonnegative functions f and g. If it is always true or never

true, give a proof. If it is sometimes true, give one example for which it is true, and one for

which it is false.

i. f(n) + g(n) = Ω(max(f(n), g(n)))

ii. f(n) = ω(g(n)) and f(n) = O(g(n))

iii. Either f(n) = O(g(n)) or f(n) = Ω(g(n)) or both.

3. (Induction, 2-page limit – your solutions should fit on two sides of 1 page). Part (a) has 10

points and part (b) has 15 points.)

(a) (Uniform shuffling) Let A[1, · · · , n] be an array of integers. A uniform shuffle of A is

a set of n random elements from A (without replacement), such that the probability of

selecting any such set is the same. Consider the following algorithm to generate a uniform

random shuffle:

3

UniformShuffle(A)

1 for i ← n downto 1

2 do j ← random integer such that 1 ≤ j ≤ i

3 exchange A[i] and A[j]

4 return A

Prove that the algorithm indeed generates a uniform random shuffle of A. What is the

running time of the algorithm, given that generating random integer takes time O(1)?

Hint: Start by thinking of what a uniform shuffle means in terms of probability.

(b) Point out the error in the following proof by induction.

Claim: Given any set of b buses, all buses lead to the same destination.

Proof: We proceed by induction on the number of buses, b.

Base case: If b = 1, then there is only one bus in the set, and so all buses in the set lead

to the same destination.

Induction step: For k ≥ 1, we assume that the claim holds for b = k and prove that it is

true for b = k + 1. Take any set B of b + 1 buses. To show that all buses lead to the same

destination, we take the following approach. Remove one bus from this set to obtain the

set B1 with just b buses. By the induction hypothesis, all the buses in B1 lead to the same

destination. Now go back to the original set and remove a different bus to obtain a the set

B2. By the same argument, all the buses in B2 lead to the same destination. Therefore all

the buses in B = B1 ∪ B2 must lead to the same destination, and the proof is complete.

4. (Divide and Conquer, 2-page limit – your solutions should fit on two sides of 1 page).

After dating for several years, Jack and Anthony have finally decided to move in together. As

part of this process, each of them wants to bring his n alphabetically sorted books over to the

new place. Due to some weird reason, they want to find out who owns the median book of the

joint book collection, which has 2n books. In this joint book collection, the median would be

the n-th book among the union of the 2n alphabetically sorted books.

Because their original book collections are already sorted, they manage to find out who owns

the median in Θ(log n). They did not have to reorder the joint book collection, but rather it

was enough for them to just query individual values from their original book collections. What

algorithm did they use? Prove that this algorithm is correct. Find the recurrence relation and

show that it resolves to Θ(log n).

4