Assignment 14 Lite: Fast Algorithms!
This assignment is due by Friday, December 10 at 5 PM under Ran's office door.

1. The Stock Market Problem [30 Points]
   

   In class we described the following problem called the "Stock Market Problem": We are given an array A of n values where A[i] indicates the value of a share of Millisoft stock on day i. That is, we have a history of n days of the values of this stock. For simplicity, assume that n is a power of 2.

   Our objective is to find the maximum profit that could be made by purchasing a single share on some day and selling on that day or later. (Buying and selling on the same day makes 0 profit, so you can't do worse than that!) Remember, you cannot sell on a day before your buy day!

   Your job is to describe and analyze a divide-and-conquer algorithm for this problem.

   1. First, give a clear description of how your algorithm works (either in English or in Ran++). Make sure to describe both the base case and the general case!
   2. Next, write a recurrence relation for the run time of your algorithm and briefly explain how you deduced this recurrence relation.
   3. Now derive a closed-form solution to your recurrence relation using the recursion tree method. Show each step of your work. Your final answer should be something like O(n) or O(n log n) or O(n^k) where n^k means "n raised to the power k".
   A note on this problem: The fastest possible solution for this problem can be obtained using the divide-and-conquer approach. There are other non-recursive solutions which are equally fast, but this problem asks you to use the divide-and-conquer approach to become familiar with how such algorithms are analyzed.


2. Fast Multiplication! [30 Points]
   In this problem we consider the problem of multiplying two n-bit numbers, x and y. (For simplicity, assume that n is a power of 2. This is generally the case anyhow in typical computer architectures, but we could easily relax this assumption.)
   1. Explain briefly why the running time of the standard algorithm (performing normal multiplication, only in base 2 rather than base 10) for this problem has running time which is O(n^2).
   2. Some fast multiplication circuits use the following clever divide-and-conquer algorithm. Divide x and y in half. Thus, x = a 2^{n/2} + b and y = c 2^{n/2} + d where a, b, c, d are n/2-bit numbers. The product of x and y, call it z, can now be computed by the following steps:

              temp1 = (a+b)(c+d)
              temp2 = ac
              temp3 = bd
              z = temp2 2^{n} + (temp1 - temp2 - temp3) 2^{n/2} + temp3
              

      Nothing for you to do here! This is just the description of the algorithm.
   3. Explain why z is in fact the product of x and y.
   4. Observe that the terms (a+b) and (c+d) may have either n/2 or n/2 + 1 bits each. For simplicity, assume for now that they each have exactly n/2 bits (the case of n/2 + 1 bits isn't hard to deal with, but let's not worry about it here). Notice that the above algorithm performs 3 multiplications of n/2 bit numbers plus some additions and shifts. (Multiplying a binary number by a number of the form 2^k can be accomplished by simply performing k bit shifts to the left! This takes just k units of time.) Now, just write down the recurrence relation (an expression for T(n), including a base case) for this algorithm.
   5. Find the big-Oh running time of the divide-and-conquer algorithm by setting up the recursion tree for the recurrence relation and then obtaining a solution. Show your work in complete detail. Your final answer shoud be O(n^k) where k is some real number.
   6. How does this algorithm's running time compare to the running time of the standard O(n^2) algorithm?

   Last modified December 2004 by Ran Libeskind-Hadas