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.

Part four focused on what the book sometimes calls the “Minimum-Cost Aborscence Problem,” which is really just focused on finding the shortest path in a graph. Although there were several proposed algorithmic solutions to this problem, my favorite was one designed by Edsger Dijstra (I'd insert it here, but there are lots of symbols that I'm not sure how to type up on this wiki – see page 138 for details). Though it didn't seem intuitive the first time I read it, I eventually got into the swing of things after reading it over a few times, taking notes in the margins, and doing some practice examples in class. I think it's just highly efficient in a satisfying way.

Overall, I definitely enjoyed part four the most, because it felt more hands-on. I really liked doing the examples of finding the most efficient paths through a graph in class, because it made me actively think through the problems rather than reading them on a page. Parts one and two were more difficult for me, simply because it seems highly improbable that the greedy algorithm will frequently be the most efficient solution in the real world, and because I generally struggle with proofs.