Description
Question 1. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and
justify your answers. [5 points]
(i) T(n) = 4T(n/3) + n log n
(ii) T(n) = 4T(n/2) + n
2√
n
(iii) T(n) = T(n/2) + 1
(iv) T(n) = 2T(n/2) + n/ log n
(v) T(n) = T(n − 1) + 1/n
Question 2.
(i) Explain how insertion sort can be expressed as a recursive procedure, write a recurrence for
the running time of this recursive procedure, and solve the recurrence to get an asymptotic
upper bound for the running time. [3 points]
(ii) For input size n > 3, will insertion sort always run slower than merge sort? Please justify
your answer with a detailed example. [2 points]
Question 3. An inversion in an array A[1..n] is a pair (i, j) of indices such that i < j, but
A[i] > A[j]. Given an array whose entries are all distinct integers, design an algorithm that
returns as its output the number of inversions in the given array. Your algorithm must run in
O(n log n) time. Please give your algorithm in pseudocode, and explain why your algorithm
runs in O(n log n) time. (Hint: Modify merge sort.)
Question 4. Inspired by the idea of cutting a deck of cards, John has designed an algorithm
that takes as input an integer array A sorted in ascending order, and gives as output a “cut”
of A performed at a random index. The pseudocode is given below:
function John Cut(A)
Require: A[1..n] is a sorted array with distinct integers.
1: k ← random integer selected from [1, . . . , n]
2: B ←array obtained after merging subarrays A[k + 1..n] and A[1..k] in this given order
3: return B.
Example: If A = [0, 1, 2, 4, 5, 7], then one possible output for John Cut(A) is [4, 5, 7, 0, 1, 2].
Design an algorithm that takes as its inputs an integer t and an integer array B, assumed to
be the output B = John Cut(A) for some sorted array A with distinct integers, and that
returns as its output the character string “yes” or “no”, representing whether t is an entry of
B. Your algorithm must run in O(log n) time. Please give your algorithm in pseudocode, and
explain why your algorithm runs in O(log n) time. [5 points]
1
Remark: The symbol ← is used frequently in pseudocode, and it means “gets” or “is assigned”.
For example, when incrementing a variable e.g. what we think of as “i = i + 1”, it would be
clearer to write “i ← i + 1” instead. (For those who write in LATEX, the command for this
symbol is \gets.)
Question 5. There are 25 horses among which you need to identify the fastest 3 horses. You
can conduct a race among at most 5 horses to find out their relative speeds. At no point in the
race are you able to determine the actual (absolute) speed of any horse. Determine the least
number of races required to identify the top 3 fastest horses, and explain how you schedule the
races. [5 points]
2