## 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)