Training Material

## Greedy Algorithms→Speculating on buffalos

Ramu was a lazy farmer. He had inherited a fairly large farm and a nice house from his father. Ramu leased out the farm land to others and earned a rather handsome income. His father used to keep a buffalo at home and sell its milk but the buffalo died a few days after his father did.

Ramu too wanted to make some money from buffalos, but in a quite a different way. He decided that his future lay in speculating on buffalos. In the market in his village, buffalos were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.

He decided that he would buy buffalos when the price was low and sell them when the price was high and, in the process, accummulate great wealth. Unfortunately his house had space for just one buffalo and so he could own at most one buffalo at any time.

Before he entered the buffalo market, he decided to examine to examine the variation in the price of buffalos over the last few days and determine the maximum profit he could have made.

Suppose the price of a buffalo over a period of 10 days varied as

```	-------------------------------------------------
Day   :  1   2   3   4   5   6   7   8   9  10
-------------------------------------------------
Price : 11   7  10   9  13  14  10  15  12  10
-------------------------------------------------
```

The maximum money he can make in this case is 13 ---

• buy on day 2, sell on day 3 (+3)
• buy on day 4, sell on day 6 (+5)
• buy on day 7, sell on day 8 (+5)

What should his strategy be?

## Solution

Suppose we plot a graph of buffalo prices as they vary day by day.

```	    15-|                                   *
14-|                      _-- *       / \
13-|                     *     \__   /   \
12-|                   /          \ /     *\
11-| *                /            *        \
10-|  \        *-__  /                        *
9-|   \     /      *
8-|    \  /
7-|      *
6-|
..
1-|
----------------------------------------------------
Day     1    2    3    4    5    6   7   8   9   10
```

Profit making intervals are those where the graph goes up. In this case, profit making intervals are days 2-3, 4-6, 7-8.

Thus, Ramu's best strategy is to buy whenever the price starts increasing and sell whenever the price starts decreasing.

Notice that this is a greedy strategy, because the decision to buy or sell is made based on the current direction of the price, without worrying about the overall trend.