Homework 2

      Problems:

1. Searching in an array of unknown length:
   Problem 2.16 from [DPV]
   
   
2. Fixed point A[i]=i:
   Problem 2.17 from [DPV]
   Note: the input is distinct integers.
   
   
3. Optimal Buy/Sell pair:
   You are given an array A[1...n] of n positive numbers that represent the
   price of a particular stock on n days. You want to buy the stock at one day
   and sell on a later day. Your goal is to determine what would have been the
   best pair of days for buying/selling. You can assume n is a power of 2.
   Here is an example: A = [10, 15, 6, 3, 7, 12, 2, 9]. Then the optimal decision
   would be to purchase on day 4 for $3 and sell on day 6 for $12.
   
   1. Warm-up -- no need to turn in this part (a)
      Give an O(n²) time algorithm for this problem.
      It is expected that the solution for part (a) might not use divide-and-conquer.
   2. Suppose you want to buy in the first n/2 days and you want to
      sell in the last n/2 days. Give an O(n) time algorithm for finding the best
      pair of days for buying/selling under this restriction. Explain your algorithm
      in words and justify/explain its running time.
   3. Give a divide and conquer algorithm with running time O(nlogn)
      for finding the best pair of days for buying/selling. (There are no restric-
      tions on the days, except that you need to buy at an earlier date than you
      sell.) Explain your algorithm in words and analyze your algorithm, including
      stating and solving the relevant recurrence.
      Hint: your algorithm should use your solution to part b.
   4. Extra credit:
      Give a divide and conquer algorithm with running time O(n)
      for finding the best pair of days for buying/selling.
      Hint: Modify the problem to obtain additional info from the subproblems
      so that you can do the "merge" part in O(1) time.
   
   
4. Linear-time Median Algorithm:
   For the deterministic O(n) time algorithm for finding the median presented in
   class, explain why breaking the array into groups of size 3 (instead of 5) does
   not work. Make sure to state the recurrence for this modified algorithm
   with groups of 3 and explain why it does not solve to O(n).
   
   
5. Poly Multiplication: Problem 2.9 from [DPV] (Practice with polynomial multiplication)
   You do not need to do inverse FFT (the last step).
   You can stop once you: multiply the results componentwise.
   
   
6. Extra credit:
   Cartesian Sum: Consider two sets A and B, each having n integers in the range from 0 to 10n.
   We wish to compute the Cartesian sum of A and B, defined by:
         C = { x + y : x∈ A and y∈ B}.
   Note that integers in C are in the range from 0 to 20n.
   We want to find the set of elements in C and also the number of times each
   element of C is realized as a sum of elements in A and B.
   Show that the problem can be solved in O(nlogn) time by
   reducing it to the polynomial multiplication algorithm.
   You just use the polynomial multiplication algorithm without modifying it.
   You need to explain what input you put into the polynomial
   multiplication algorithm and what you do with the output
   to get the solution to the Cartesian Sum problem.
   
   Example: A=[1,2,3], B=[2,3]
   then in this case C=[3,4,5,6]
   And the solution to the Cartesian Sum problem is:
     3 appears and is obtainable in 1 way
     4 appears and is obtainable in 2 ways
     5 appears and is obtainable in 2 ways
     6 appears and is obtainable in 1 way