Description
Homework Problems
1. (15 points) Consider the problem of computing N! = 1 · 2 · 3 · · · N.
(a) If N is an n-bit integer, how many bits long is N! in Θ() notation?
(b) Give an algorithm to compute N! and analyze its running time. Assume that the time
to multiply two n-bit integers is O(n
2
).
x2 < x3 ?
x1< x2 ?
x1< x3 ?
no
x1< x3 ? x2
, x1
, x3
x2 < x3 ?
yes
yes no yes no
x1
, x2
, x3
x3
, x1
, x2
yes no
x1
, x3
, x2
x2
, x3
, x1
x3
, x2
, x1
yes no
depth 0 (root level)
depth 1
depth 2
depth 3
Figure 1: A tree corresponding to a comparison-based sorting algorithm on input x1, x2, x3.
2. (35 points) On sorting
(a) (15 points) A lower bound for comparison-based sorting
You may view a comparison-based sorting algorithm as a binary tree. For example, the
tree in Figure 1 sorts 3 integers x1, x2, x3: it first compares x1 to x2; if x1 < x2, it
compares x2 to x3, else is compares x1 to x3, etc. Each leaf corresponds to a possible
permutation of the 3 numbers. For example, if x1 < x2 < x3, we get the leaf labelled
x1, x2, x3.
Suppose you want to sort n integers.
i. (2 points) Argue that every possible permutation of the n numbers must appear as
a leaf in the tree corresponding to a sorting algorithm.
ii. (2 points) Fill in the missing number in the following sentence:
Thus the tree has at least . . . leaves.
iii. (3 points) The worst-case time complexity of the sorting algorithm is given by the
maximum number of comparisons performed by the algorithm. What does the latter
quantity correspond to in the tree?
iv. (3 points) Consider a binary tree of depth d. Give with a proof an upper bound on
the number of leaves of the tree.
v. (5 points) Derive a lower bound for the worst-case time complexity of a comparisonbased sorting algorithm.
(b) (17 points) Give an algorithm that sorts any array of n integers x1, . . . , xn in O(n + D)
time, where D = max
i
xi − min
i
xi
.
(c) (3 points) Suppose D is small (that is, O(n)). Does the algorithm you proposed in part
(b) contradict the lower bound you derived in part (a)?
3. (25 points) In the table below, indicate the relationship between functions f and g for each
pair (f, g) by writing “yes” or “no” in each box. For example, if f = O(g) then write “yes”
in the first box. Here logb x = (log2 x)
b
.
f g O o Ω ω Θ
log2 n 6 log n
√
log n (log log n)
3
4n log n n log (4n)
n
3/5 √
n log n
5
√
n + log n 2
√
n
n
54
n 5
n
√
n2
n 2
n/2+log n
n log (2n)
n
2
log n
n! 2
n
log n! (log n)
log n
4. (25 points) The Hadamard matrices H0, H1, H2, . . . are defined as follows:
• H0 is the 1 × 1 matrix h
1
i
• For k > 0, Hk is the 2k × 2
k matrix
Hk =
”
Hk−1 Hk−1
Hk−1 −Hk−1
#
Let ν be a column vector of length n = 2k
. Can you compute the matrix-vector product
Hkν faster than the straightforward algorithm that requires O(n
2
) time? (Assume that all
the numbers involved are small enough that basic arithmetic operations like addition and
multiplication take unit time.)
5. (30 points) Consider a complete binary tree T on n = 2d − 1 nodes, for some integer d > 1.
Each node v in T is labeled with a real number xv; all xv are distinct. A node v in T is a
local minimum if its label xv is less than the label xu for every node u joined to v by an edge.
You are given such a complete binary tree T but the labeling is only specified in the following
implicit way: for each node v, you can determine xv by probing the node v. Give an efficient
algorithm to find a local minimum of T. (You may assume that each probe takes constant
time.)
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.
