Please note that this assignment is due at an unusual time - Wednesday, May 4 at 5 PM. With the exception of one part of problem 3, this is a written assignment and should be slid under Ran's office door (Olin 1245) by Wednesday at 5 PM. The first part of problem 3 involves some programming and this code should be submitted using cs60submit, also by Wednesday at 5 PM.
Throughout this assignment, you will be analyzing the running time of algorithms. We will be interested in the worst-case analysis. (The best case isn't interesting and the average case is usually very hard to analyze!) Also, you will need to express the worst-case running time using big-Oh notation. Finally, make sure to show all of your work in each written problem. Explain each step carefully and don't skip steps.
for (int i=1 ; i≤n ; i *= 2)
for (int j=0 ; j<i ; ++j)
// constant time work here
for (int i=1 ; i≤n ; ++i)
for (int j=1 ; j<i ; j *= 2)
// constant time work here
reachable(A,A,G) => 1; // vertex A can reach A in any graph G!
reachable(A,B,[]) => 0; // vertex A cannot reach B if G is empty!
reachable(A,B,[[x,y]|R]) => reachable(A,B,R) ||
(reachable(A,x,R) && reachable(y,B,R));
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 in your analysis that n is a power of 2. (When you implment this program in the next problem you code should work for all values of n.)
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 "fast" divide-and-conquer algorithm for this problem. Your algorithm must use divide-and-conquer and it must be asymptotically faster than O(n^2).
Your first task is to implement your fast divide-and-conquer algorithm for the Stock Market Problem (see Problem 2 above). Your code should be written in Java. Your code should work for any positive number of stock values (not just powers of 2).
We have provided several files for you in the directory /cs/cs60/assignments/assignment14/. In particular, you will be adding your function called fast to the file StockMarket.java which we have provided. The file SMHelper.java simply contains some code for reading in files and generating random arrays of stock values. There is no need to modify this file. The files test1 and test2 are sample stockmarket value files.
Notice that StockMarket.java has explanatory comments in its header. Please read them carefully. You'll notice that the "slow" O(n^2) algorithm has already been implemented for you and you must only implement a "fast" algorithm. You'll also notice that there are two ways to run the program, one for testing your "fast" algorithm for correctness using a file of stockmarket values, and the other for running a large number of tests on large arrays to compare the "slow" and "fast" algorithms.
For full credit, your "fast" algorithm must be correct and must be very significantly faster than the "slow" algorithm both in theory and in practice.
A note about the running times reported by StockMarket.java: The running times that you'll see are "wall clock" time. That is, how much time elapsed from the beginning of the function call to the end of the function call. The actual running time (or "CPU time") may be less than this, since turing shares its resources between many programs running at the same time. Therefore, if you run StockMarket.java in the middle of the night it might run slower than if you run it in the middle of the day (since presumably more people are using turing in the middle of the night than in the middle of the day)! However, the times that are reported give a reasonably accurate comparison of the running times of the "slow" and "fast" algorithms.
The second part of this problem is short and should be submitted in writing. Plot the run times of the "slow" and "fast" algorithms as reported by the program (you may use any plotting software you like or do this by hand). Then, write down two equations that fit each of the two "curves" reasonably well. For example, an equation might be something like "8 n^2" (this would be a O(n^2) algorithm). Your equations should fit the data relatively well and should be plotted on the graph too! Make sure to label your data and curves (equations) so that we understand what each one means. In all, you'll have two plots of empirical data (one for the "slow" algorithm and one for the "fast" algorithm) and two theoretical curves (equations) which fit the data reasonably well. You'll also give the mathematical equations for these curves.
Keep in mind that the theoretical curves (equations) must be consistent with the big-Oh theoretical analyses of the algorithms! That is, for the slow algorithm, your equation should have a n^2 dominant term and for the fast algorithm, the dominant term should be smaller than n^2! The actual constants (coefficients) in your equations may depend slightly on what time of day or night you performed your experiments, but that's OK.
Professor Dee Videanconker has proposed the following alternate divide-and-conquer approach to multiplying two n-bit numbers x and y. Notice that x has n/2 "upper bits" which we'll call "a" and n/2 "lower bits" which we'll call "b". Similarly, dividing y in two parts gives us the upper n/2 bits, which we'll call "c", and the lower n/2 bits, which we'll call "d". So, x = a 2^{n/2} + b and y = c 2^{n/2} + d. What's going on here? Notice that multiplying "a" by 2^{n/2} "shifts" it by n/2 positions. The number "a" by itself is a n/2 bit number. After the multiplication by 2^{n/2}, the bits of "a" have been "promoted" so that we now have a n-bit number in which the first n/2 bits are the bits of "a" and the last n/2 bits are all 0's. Now, adding "b" to this gives us a n-bit number in which the first n/2 bits are "a" and the second n/2 bits are "b". That is, we now have written x in terms of "a" and "b". We do the analogous thing for expressing y in terms of "c" and "d".
So, back to Professor Videanconker's algorithm! The algorithm works like this: Divide x into two n/2-bit numbers "a" and "b" and similarly divide y into two n/2 bit-numbers "c" and "d". Now, xy = (2^{n/2}a + b)(2^{n/2}c + d) = 2^{n}ac + 2^{n/2}(ad + bc) + bd. We compute "ab" using a recursive call (now on numbers that are n/2 bits long!) and similarly we compute "ad", "bc", and "bd". After the recursive calls are complete we do the multiplications by 2^{n} and 2^{n/2} followed by some addition. Notice that multiplying by 2^{k} is just the same as adding k 0's to the end of the number. This can be done in k time steps. Similarly, adding two j-bit numbers can be done in j time 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.
Last modified April 2005 by Ran Libeskind-Hadas