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
- an English language paragraph
that describes your algorithm (a comment in the code will do),
- an analysis of the running time of both algorithms
- your source code that implements the algorithms
- sample runs for both algorithms (the brute-force algorithm
will not run on the larger inputs, so don't bother)
- 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.