Description
1. 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.
2. Hidden surface removal is a problem in computer graphics that scarcely needs an introduction: when
Woody is standing in front of Buzz, you should be able to see Woody but not Buzz; when Buzz is standing
in front of Woody, … well, you get the idea.
The magic of hidden surface removal is that you can often compute things faster than your intuition
suggests. Here’s a clean geometric example to illustrate a basic speed-up that can be achieved. You
are given n nonvertical lines in the plane, labeled L1, L2, · · · , Ln with i
th line specified by the equation
y = aix + bi
. We will make the assumption that no three of the lines all meet at a single point. We say line
Li is uppermost at a given x-coordinate x0 if its y-coordinate at x0 is greater than the y-coordinates of all
the other lines at x0, ∀j ̸= i, aix0 + bi > ajx0 + bj . We say line Li is visible if there is some x-coordinate at
which it is uppermost, intuitively some portion of it can be seen if you look down from y = ∞.
Give an algorithm that takes n lines as input and in O(nlogn) time returns all of the ones that are visible.
3. Assume that you have a blackbox that can multiply two integers. Describe an algorithm that when
given an n-bit positive integer a and an integer x, computes x
a with at most O(n) calls to the blackbox.
4. 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(nlogn) 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)
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))
6. Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you
with the following problem. They have a collection of n bank cards that they’ve confiscated, suspecting
them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with
some encrypted data, and it corresponds to a unique account in the bank. Each account can have many
bank cards corresponding to it, and we’ll say that two bank cards are equivalent if they correspond to
the same account. It’s very difficult to read the account number off a bank card directly, but the bank
has a high-tech equivalence tester that takes two bank cards and, after performing some computations,
determines whether they are equivalent.
Their question is the following: among the collection of n cards, is there a set of more than n/2 of them
that are all equivalent to one another? Assume that the only feasible operations you can do with the cards
are to pick two of them and plug them in to the equivalence tester. Show how to decide the answer to
their question with only O(nlogn) invocations of the equivalence tester.