You have to cut a log into several pieces. To do so, you bring it to a company that charges money according to the length of the log being cut. Their cutting method means that only one cut can be made at a time. For example, suppose that a log of length 10 meters has to be cut at positions 2, 4, and 7 from one end. There are several ways to do this. One way is to first cut at 2, then 4, and then at 7. This gives a price of 10 + 8 + 6 = 24 because the first piece was 10 meters in length, the second was 8 meters, and the third was 6 meters in length. Another way is to cut at 4, then at 2, then at 7. This would give a total price of 10 + 4 + 6 = 20, which is a cheaper price.

One could consider several different greedy algorithms for this log cutting problem.

(a) Provide a counterexample to show that a greedy algorithm that always makes the median cut first is not correct. (If n cuts have to be made, the median cut is the n/2^th cut, where ever it is located.

(b) Provide a counterexample to show that a greedy algorithm that always makes the cut closest to the center of the log first is not correct.

(c) Propose another simple, greedy way of choosing the first cut, and show that that does not work either.