Assignment 6

Due: Friday, March 14

Late Homeworks will not be accepted after Monday, March 17th, 11am

1. Solving Recurrences (25 points)

Solve the following Recurrences. You may use the Masters Recurrence, but be sure to state which case you use and why, and show how you get your answer

  1. T(n) = T(n/2) + c n
  2. T(n) = 3 T(n/4) + c n
  3. T(n) = 3 T(n/4) + c n2
  4. T(n) = 4 T(n/3) + c n2
  5. T(n) = 25 T(n/5) + c n2

2. Dynamic Programming (35 points)
You are interested in analyzing trends in stock prices. In particular, you want to see if two stocks have similar behaviors -- if when one stock price goes up, the other stock price goes up as well; and when one goes down, the other goes down as well. For example, we might see some similar trends in prices for airlines and trucking industries, as they both respond to gas prices. One problem is, their responses might not be at the exact same time (eg., though both respond to an increase in gas prices, airlines might respond in 2 weeks, while trucking industries will respond in 1 week).

More formally, we'll let a set of stock prices be given by list of integers, with one price per day. For two sets of stock prices X = x1x2...xm and Y = y1y2...yn, we define a matching between the two stock prices to be a set of pairs (xi, yj), where

  1. every price is one sequence is matched to at most one price in the other sequence.
  2. if the matching has pairs (xi,yj) and (xk, yl), then either i < k and j < l, or i > k and j > l (eg., no crossings).
We want to find the matching that makes the two sequences as "close" as possible. We'll define the distance between the stocks as the difference between the matched pairs, plus a penalty of 10 for every unmatched price. For example, given X = (10,15,20,30,24,15,1,7,19) and Y = (10,12,16,20,25,30,35,12,2,18) then the matching: 
X    = 10,--,15,20,--,30,--,24,15, 1, 7,19
Y    = 10,12,16,20,25,30,35,--,12, 2,--,18
Dist =  0,10, 1, 0,10, 0,10,10, 3, 1,10, 1
has a distance of 56, while this matching: 
X    = 10,--,15,20,--,30,24,15, 1, 7,19
Y    = 10,12,16,20,25,30,35,12, 2,--,18
Dist =  0,10, 1, 0,10, 0,11, 3, 1,10, 1
has a distance of 47.

We want to find the matching with the smallest distance. It can be found with a dynamic programming approach. Give the recurrence to solve this problem.

3. NP (40 points)
The MaxCut problem is the following: given an undirected graph G=(V,E) and an integer k, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets V1 and V2 so that k or more edges have one end in V1 and the other end in V2?

  1. Prove that MaxCut is in NP.
  2. Give an algorithm for MaxCut and analyze its running time. (A non-polynomial-time algorithm shouldn't be a big surprise.)