Description
1. [20 points] Solve the following recurrences by giving tight Θ-notation bounds in terms of n for
sufficiently large n. Assume that T(n) represents the running time of an algorithm, i.e., T(n) is a
positive and non-decreasing function of n.
For each part below, briefly describe the steps along
with the final answer:
a. 𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛
2
𝑙𝑜𝑔𝑛
b. 𝑇(𝑛) = (4. 01)𝑇(𝑛/2) + 𝑛
2
𝑙𝑜𝑔𝑛
c. 𝑇(𝑛) = 6000𝑇(𝑛/2) + 𝑛
6000
d. 𝑇(𝑛) = 10𝑇(𝑛/2) + 2
𝑛
e. 𝑇(𝑛) = 2𝑇( 𝑛) + 𝑙𝑜𝑔
2
𝑛
2. [25 points] Solve Kleinberg and Tardos, Chapter 5, Exercise 5.
3. [20 points] Assume that you have a blackbox that can multiply two integers. Describe an
algorithm that when given an n-bit positive integer 𝑎 and an integer 𝑥, computes 𝑥 with at most
𝑎
𝑂(𝑛) calls to the blackbox.
4. [25 points] A city’s skyline is the outer contour of the silhouette formed by all the buildings in
that city when viewed from a distance. A building Bi is represented as a triplet (Li
, Hi
, Ri) where
Li and Ri denote the left and right x coordinates of the building, and Hi denotes the height of the
building. Describe an O(n log n) algorithm for finding the skyline of n buildings.
For example, the skyline of the buildings {(3, 13, 9),(1, 11, 5),(12, 7, 16),(14, 3, 25),(19, 18,
22),(2, 6, 7),(23, 13, 29),(23, 4, 28)} is {(1, 11),( 3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3),
(23, 13), (29, 0)}.
(Note that the x coordinates in a skyline are sorted)
