(Due at the beginning of
class on 10/31/11)

This problem set will be graded out of 50 points. It
will count for 20% of your final grade.

1) Random questions

a) Consider the following heuristic
for the interval scheduling problem: pick the interval that overlaps the fewest
remaining intervals. Give a counterexample to this heuristic. Your
counterexample should not need to break any ties. [1]

b) What is a heap? Describe the
operations ExtractMin and ChangeKey.
Analyze their running times. [4]

c) Given a point (x’, y’) and a
line y = ax + b, the error is defined to be (y’ – ax’ –b)^{2}.
Given n points and a line the error is defined to the sum of errors for each
point.

i)
Given n points, the line with the lowest error is called the “line of
best fit.” Find equations for a and b for the line of
best fit given n points p_{i} = (x_{i}, y_{i}). [2]

ii) Given n points p_{i} = (x_{i}, y_{i}) let e_{i,j}
be the error to the best fit line of the point p_{i}, p_{i+1}, …p_{j}. Given O(n) preprocessing
time show how any e_{i,j} can be computed in O(1)
time. [3]

2) Median I

a) What happens to the median
finding algorithm if we divide into groups of 3? [2]

b) What happens to the median
finding algorithm if we divide into groups of 7? [2]

c) Given two ordered arrays
with n elements each, give an O(log n) algorithm to
find the median of the combined set of 2n elements. [4]

d) Given an O(n)
algorithm to find the n/3th largest element in a list of unordered elements.
[2]

3) Median II

a) Consider the following game:
Two players A and B are each given a set of n (not necessarily
unique) numbers. Each number is represented using log n bits. A does not know
B’s numbers and B does not know A’s numbers. Give a protocol whereby A and B
can learn the median of their combined set of 2n numbers using O(log n) communication bits. [6]

b) Given n distinct elements x_{1}, x_{2}, … x_{n} with associated positive weights w_{1}, w_{2}, …w_{n}, ∑ w_{i} = 1, let the weighted
median be the element x_{k} such that sum of w_{i} for all x_{i} < x_{k} is less than ½ and the sum of w_{i} for all x_{i} > x_{k} is at most ½. Show how the weighted median of n
numbers can be computed in O(n) time. [4]

4) Shortest Paths

a) The bottleneck capacity of a
path is the smallest capacity of any edge in the path. The bottleneck capacity
of (u, v) is the largest bottleneck capacity of any path from u to v. Give an O(n^{3}) algorithm to find the bottleneck capacity for each
pair u, v in a directed capacitated graph. [2]

b) Show how the shortest paths
can be recovered in Floyd-Warshall. What is the complexity of your scheme? [3]

c) Why can’t matrix
multiplication be used to compute all-pairs shortest paths in sub-cubic time?
[2]

d) Given a directed graph with
nodes s and t, give an efficient algorithm to find the number of shortest paths
from s to t. Prove its correctness and analyze its running time. [3]

5) Dynamic Programming

a) Give an O(n^
(log_{2}3)) algorithm to compute the
product of two n-bit numbers. [3]

b) Given two strands of DNA
(i.e. strings over the alphabet {A, T, C, G}), one of length m and another of
length n, show how the longest common subsequence can be computed in O(mn) time using only O(m+n) space.
[3]

c) You are given a convex (not
necessarily regular) n-gon in the plane. A
triangulation of the n-gon is a collection of
diagonals so that each internal face is a triangle. The length of a
triangulation is the sum of the lengths of its diagonals. Give an efficient
algorithm to find a triangulation of minimum length. [4]