EE3980 Algorithms
Homework 6. Stock Short Selling Revisited
In homework 4, the single-sell-single-buy stock short selling problem was transformed into a
maximum subarray problem. And, two algorithms were used to solve the problem. Many people
have noticed the inefficiency in the brute-force approach, which possesses a time complexity of
O(n
3
). Thus, in this homework you have a chance to fix the problem. There are two parts in
this homework:
1. Please modify Algorithm (3.1.12) to achieve O(n
2
) complexity.
Note that is may need to deviate from using the maximum subarray approach.
2. Please design an algorithm that has lower than the divide-and-conquer approach, if you
can. If you find it impossible, please give the reason why.
As in Homework 4, please use the Google stock data files to demonstrate the complexities of
your algorithms. The number of repetitions in measuring the CPU time should not be less than
5000. The output of your program should also follow that of homework 4. In addition, please
compare the CPU times for all the implemented algorithms for homework 4 and 6.
Notes.
1. One executable and error-free C source file should be turned in. This source file should be
named as hw06.c.
2. A report file in pdf format is also needed. This file should be named as hw06a.pdf.
3. Submit your hw06.c and hw06a.pdf on EE workstations using the following command:
∼ee3980/bin/submit hw06 hw06.c hw06a.pdf
where hw06 indicates homework 6.
4. Your report should be clearly written such that I can understand it. The writing, including
English grammar, is part of the grading criteria.
5. The CPU time per iteration of the second algorithm, if any, may be used to determined
part of the grades of this homework.
1
