Description
1. (15 points) Given an undirected graph G = (V, E) and a specific edge e ∈ E, give an efficient
algorithm that determines whether G has a cycle that contains e.
2. (35 points) You are given a directed graph G = (V, E) in which each node u ∈ V has an
associated price pu which is a positive integer. Define the array cost as follows: for each
u ∈ V ,
cost[u] = price of the cheapest node reachable from u (including u itself)
For instance, in the graph below (with prices shown for each vertex), the cost values of the
nodes A, B, C, D, E, F are 2, 1, 4, 1, 4, 5 respectively.
A C E
B D F
2 6 4
3 1 5
Your goal is to design an algorithm that fills in the entire array cost.
(a) (20 points) Give a linear-time algorithm that works for directed acyclic graphs.
(b) (15 points) Extend this to a linear-time algorithm that works for all directed graphs.
3. (25 points) You want to determine the probability of obtaining exactly k heads when n biased
coins are tossed independently, where the i-th coin has known probability pi of coming up
heads.
Given n, k, and {p1, . . . , pn}, design and analyze an algorithm for this task that runs in time
O(nk). (Assume that you can multiply and add two numbers in [0, 1] in O(1) time.)
4. (30 points) A hotel chain is considering opening a series of hotels along a long highway. The
n possible locations are on a straight line, and the distances of these locations from the start
of the highway are m1, m2, . . . , mn, in increasing order of miles. The constraints are
• At each location, at most one hotel may open. The expected profit from opening a hotel
at location i is pi > 0.
• Any two hotels should be at least k miles apart, for some integer k > 0.
Give an efficient algorithm to compute the maximum expected total profit subject to the
given constraints. Hint: Try to give a o(n
2
) algorithm.
5. (35 points) There is a number pyramid. The top floor has 1 positive integer. The second
floor has 2 positive integers, the third floor 3, and so on and so forth.
Here is an example of a pyramid with 4 floors:
6
3 8
7 1 0
2 6 4 4
You start from the top floor. At each step, you can go either diagonally down to the left or
diagonally down to the right. This way you can form a route from the top of the pyramid to
its base. Note that there are multiple routes that end somewhere in the base of the pyramid.
Your goal is to maximize the sum of the integers on any route.
Design and analyze an efficient algorithm to compute the maximum sum on any route from
the top to the base of the pyramid. You should also return an optimal route. You may assume
that there are n floors in the pyramid.
In the above example, the maximum sum is 22 achieved by route 6 → 3 → 7 → 6.
RECOMMENDED exercises: do NOT return, they will not be graded.
1. A server has n customers waiting to be served. The service time for customer i is ti minutes.
So if the customers are served in order of increasing i, the i-th customer spends Pi
j=1 tj
minutes waiting to be served.
Given n, {t1, t2, . . . , tn}, design an efficient algorithm to compute the optimal order in which
to process the customers so that the total waiting time below is minimized:
T =
Xn
i=1
(time spent waiting by customer i)
2. https://leetcode.com/problems/climbing-stairs/. Contributed by Michael Jan; everyone is encouraged to work on this problem before attempting the homework problems.
3. Give an efficient algorithm to compute the length of the longest increasing subsequence of a
sequence of numbers a1, . . . , an. A subsequence is any subset of these numbers taken in order,
of the form ai1
, ai2
, . . . , aik where 1 ≤ i1 < i2 < . . . < ik ≤ n and an increasing subsequence
is one in which the numbers are getting strictly larger.
For example, the longest increasing subsequence of 5, 2, 8, 6, 3, 6, 7 is 2, 3, 6, 7 and its length is
4.
4. Consider an array A with n numbers, some of which (but not all) may be negative. We wish
to find indices i and j such that
X
j
k=i
A[k]
is maximized. Give an efficient algorithm for this problem.
5. Given two strings x = x1x2 · · · xm and y = y1y2 · · · yn, we wish to find the length of their
longest common substring, that is, the largest k for which there are indices i and j such that
xixi+1 · · · xi+k−1 = yjyj+1 · · · yj+k−1.
Give an efficient algorithm for this problem.
