Graded Questions
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𝑛
𝑇(𝑛) = 2𝑇( 𝑛) + 𝑙𝑜𝑔2𝑛
e.
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)
Ungraded Questions
5. Emily has received a set of marbles as her birthday gift. She is trying to create a staircase shape with her marbles. A staircase shape contains k marbles in the kth row. Given n as the number of marbles help her to figure out the number of rows of the largest staircase she can make.(Time complexity <O(n))
For example a staircase of size 4 looks like:
*
* *
* * *
* * * *
Table 0.1: Staircase of size 4
6. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.
