Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2018:journals:martinj:4.1.4 [2018/02/27 04:33] – created martinj | courses:cs211:winter2018:journals:martinj:4.1.4 [2018/02/27 04:39] (current) – martinj | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| - 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. | - 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. | ||
| - 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 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 " | ||
| + | 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. | ||
