# Problem Set - III10/12/11

(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]