CST370: Design and Analysis of Algorithms, Week 7
Week 7 This week we covered dynamic programming, Warshall’s Algorithm, Floyd’s Algorithm, Greedy algorithms, and Prim’s Algorithm. Dynamic programming made sense once I got the idea that you are basically keeping track of answers to smaller problems so you do not have to keep solving the same thing over and over. The examples with Fibonacci and the coin problems helped make that idea a lot easier to follow. Warshall’s and Floyd’s Algorithms were also not too bad once I got used to the tables. I understood the general idea of updating the matrix step by step and using previous information to figure out whether a path exists or what the shortest distance is. The greedy algorithm idea was pretty straightforward. Making the best choice available at each step made sense, especially with the change-making example. Oddly enough, Prim’s Algorithm gave me the most trouble this week. Visually, I could look at the graph and usually tell which edge should be chosen next, but the table confused me ...
