Assignment #2: Stock Market Optimality

Problem Statement

The input is an array of positive numbers. Find two numbers a[i] and a[j] in the array such that j is greater than or equal to i and a[j]/a[i] is maximized. Notice that if the array represents a daily closing stock price, then what you are looking for is the optimal buying point (i) and selling point (j), so as to maximize your percentage gain.

Inputs

The inputs will be contained in 4 separate files. There will be one number per line. Checking this is easily done using string streams (Appendix A.7.1); (Visual C++ users should check the compiler bugs also.) You must get the file name(s) from command line argument(s). If you do not know how to use command line arguments, reread Appendix A.6.6. You may not make any assumptions about the size of the inputs; resize a Vector as needed. Of course, you must report any bad lines in the input. After issuing a warning, skip the bad line, as if it never occurred.

What You Have To Do

There is a trivial brute-force algorithm to solve the problem. You will need to write code that uses this algorithm. You must then design a significantly faster algorithm, and write code for that too. Significantly faster means that it has better Big-Oh performance; there is no credit if your second algorithm does not successfully produce a correct answer for all the inputs. The inputs are of type double, but your functions that solve the problem should be templates that take an arbitrary Number type. Here is the prototype: 
template <class Number>
Number BestGain( const Vector<Number> & a, int & bestStart, int & bestEnd );

Submission Details

Your submission should include
  1. an English language paragraph that describes your algorithm (a comment in the code will do),
  2. an analysis of the running time of both algorithms
  3. your source code that implements the algorithms
  4. sample runs for both algorithms (the brute-force algorithm will not run on the larger inputs, so don't bother)
  5. an indication of how long each algorithm takes on the inputs that it runs on (use either the time command or the profiler prof, which is described in Section 1.6.
I will provide four good test cases of various sizes Look for them on September 9. Figuring out how to get timing information is part of the assignment. Don't ask me how to do it; I won't tell you.

Due Date

This program is due on September 16.