Description
1. (20 points) Consider the following recursive algorithm. On input a list of distinct numbers,
the algorithm runs in three phases. In the first phase, the first d2/3e elements of the list are
sorted recursively; when the list has size 2, return the list if ordered, otherwise swap. In the
second phase, the last d2/3e elements are sorted recursively. Finally, in the third phase, the
first d2/3e elements are sorted recursively again.
Give pseudocode for this algorithm, prove its correctness and derive a recurrence for its
running time. Use the recurrence to bound its asymptotic running time. Would you use this
algorithm in your next application to sort?
2. (30 points) In this problem, we will analyze an algorithm that finds an item close enough to
the median item of a set S = {a1, . . . , an} of n distinct numbers. Specifically, the algorithm
finds an item ai such that at least n/4 items are smaller than ai and at least n/4 items are
greater than ai
.
Algorithm 1
Randomized Approximate Median(S)
1: Select an item ai ∈ S uniformly at random
2: rank = 1
3: for j = 1 to n do
4: if aj < ai then rank = rank + 1
5: end if
6: end for
7: if n/4 ≤ rank ≤ 3n/4 then return ai
8: else return error
9: end if
(a) What is the running time of this algorithm?
(b) What kind of randomized algorithm is Randomized Approximate Median and why?
What is the success probability of this algorithm, that is, the probability that it will
return an element (and not error)?
(c) How can you improve the success probability of the algorithm to over 99%? What is the
running time of the new algorithm?
3. (30 points) Suppose that a sequence of items passes by one at a time. We want to maintain a
sample of one item with the property that it is uniformly distributed over all the items that
we have seen so far. Moreover we do not know the total number of items in advance and we
cannot store more than one item at any time.
(a) Consider the following algorithm. When the first item appears, we store it. When the
k-th item appears, we replace the stored item with probability 1/k. Show that this
algorithm solves the problem.
(b) Now suppose that when the k-th item appears, we replace the stored item with probability 1/2. What is the distribution of the stored item in this case?
4. (40 points) The Fibonacci numbers are defined by the recurrence
Fn =
0, if n = 0
1, if n = 1
Fn−1 + Fn−2, if n ≥ 2
(a) (6 points) Show that Fn ≥ 2
n/2
, n ≥ 6.
(b) Assume that the cost of adding, subtracting, or multiplying two integers is O(1), independent of the size of the integers.
i) (6 points) Give an algorithm that computes Fn based on the recursive definition
above. Develop a recurrence for the running time of your algorithm and give an
asymptotic lower bound for it.
ii) (8 points) Give a non-recursive algorithm that asymptotically performs fewer additions than the recursive algorithm. Discuss the running time of the new algorithm.
iii) (20 points) Given an algorithm to compute Fn in O(log n) time using only integer
additions and multiplications.
(Hint: Observe that
”
F2
F1
#
=
”
1 1
1 0#
·
”
F1
F0
#
.
Can you build on this to compute Fn?)
RECOMMENDED EXERCISES (do NOT submit, they will not be graded)
1. Give tight asymptotic bounds for the following recurrences.
• T(n) = 4T(n/2) + n
3 − 1.
• T(n) = 8T(n/2) + n
2
.
• T(n) = 6T(n/3) + n.
• T(n) = T(
√
n) + 1.
2. Show that, if λ is a positive real number, then f(n) = 1 + λ + λ
2 + . . . + λ
n
is
(a) Θ(1) if λ < 1.
(b) Θ(n) if λ = 1.
(c) Θ(λ
n
) if λ > 1.
Therefore, in big-Θ notation, the sum of a geometric series is simply the first term if the series
is strictly decreasing, the last term if the series is strictly increasing, or the number of terms
if the series is unchanging.
