(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 pi = (xi, yi). [2]
ii) Given n points pi = (xi, yi) let ei,j
be the error to the best fit line of the point pi, pi+1, …pj. Given O(n) preprocessing
time show how any ei,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 x1, x2, … xn with associated positive weights w1, w2, …wn, ∑ wi = 1, let the weighted
median be the element xk such that sum of wi for all xi < xk is less than ½ and the sum of wi for all xi > xk 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(n3) 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^
(log23)) 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]