Problem Set - III 10/12/11

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


CS 7800 Advanced Algorithms

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 Bs numbers and B does not know As 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 cant 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]