Description
EE3980 Algorithms
Most investors make profit in stock market by buying stocks at a low price and then selling
them at a higher price. The positive price difference is then the profit earned. It was shown that
both Algorithms (3.1.12) and (3.1.13) can be used to find the maximum earning for one-buyone-sell stock trading. In this homework you need to modify both algorithms to make maximum
profit with one-sell-one-buy trading: stock short-selling. In this scheme, a trader borrows some
stocks and sells them at a high price. Later on he/she will need to buy the same amount of stocks
back, hopefully at a lower price. The price difference is then the earning he/she makes.
The history of Google stock (GOOGL) closing price is given in 9 files, s1.dat – s9.dat.
Again the first line of each file contains the number of data entries in that file. Followed by
the date and the closing price of that day. Assuming only one sell and one buy is performed,
using the maximum subarray algorithms, please find the selling day and the price, the buying
day and the price, and the earning made per share. A typical program output is as following.
$ a.out < s1.dat
N = 16
Brute-force approach: CPU time 3.09944e-06 s
Sell: 2004/8/23 at 54.8694
Buy: 2004/9/3 at 50.1598
Earning: 4.7096 per share.
Divide and Conquer: CPU time 3.75986e-07 s
Sell: 2004/8/23 at 54.8694
Buy: 2004/9/3 at 50.1598
Earning: 4.7096 per share.
Note that the CPU time is also measured for both algorithms. However, Algorithm (3.1.12)
is executed only once, but Algorithm (3.1.13) is executed 1000 times to get the average CPU
time.
As usual, you should analyze both algorithms, implement them, execute them using the
data files provides, record the CPU times and correlate the performance to your analyses. Also,
please report your observations and conclusions.
1
Notes.
1. One executable and error-free C source file should be turned in. This source file should be
named as hw04.c.
2. A report file in pdf format is also needed. This file should be named as hw04a.pdf.
3. Submit your hw04.c and hw04a.pdf on EE workstations using the following command:
∼ee3980/bin/submit hw04 hw04.c hw04a.pdf
where hw04 indicates homework 4.
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. Since the date (year, month, day) and price information should be kept for the program, it
is recommended to use the structure as following.
typedef struct sSTKprice {
int year, month, day;
double price, change;
} STKprice;
2
