This is an old revision of the document!

Chapter four largely focused on greedy algorithms. Parts one and two helped me understand how to prove if/when a greedy algorithm is, in fact, the optimal solution to a problem.

1. Part one had its own method to help me do so called the greedy algorithm stays ahead. It focuses on measuring the progress of the greedy algorithm each step of the solution and comparing it to any other algorithm. The logic behind this is that, if we can prove that the greedy algorithm is more efficient than alternative algorithms on literally each step of the process, then the greedy algorithm must be more efficient overall.
2. Part two also had its own approach to help me figure out how to prove if/when a greedy algorithm is the optimal solution. This method is called the exchange argument. It calls for the programmer look at any alternate solutions to the problem (other than the greedy algorithm, of course). Then, the programmer must slowly transform that algorithm into the greedy algorithm, checking along the way if the efficiency is at all reduced in the process. If the runtime increases at any step while the programmer is transforming the solution into the greedy algorithm, then naturally the solution at hand is more efficient. However, if the programmer can show that no part of this process hindered the efficiency of the program, then he/she may come to the conclusion that the greedy solution is equally as efficient as the solution at hand.