CST370 - Week 7

Wrapping up our 7th week in Design & Analysis of Algorithms, we covered some new non-comparison sorting algorithms: Counting Sort and Radix Sort. Then we had a lecture on Dynamic Programming, whose basic concept is to break a problem into smaller subproblems and optimize by storing the results of those subproblems so we don't compute the same ones multiple times.

Next, we went over Warshall's Algorithm and Floyd's Algorithm, which look quite similar but have different purposes. Warshall's algorithm finds the transitive closure; in other words, it determines whether there is a path between two vertices. In contrast, Floyd's algorithm is used to find the shortest paths/minimum cost between vertices.

Lastly, we discussed the Greedy Technique, which involves building a solution step-by-step by always making the choice that seems best at the moment, with the hope that these local choices lead to an optimal overall outcome.

Next week we have our final exam, which I'm a bit nervous about. To prepare for it, I plan to review all the material we've covered so far in the previous weeks and work through previous problems in our quizzes and midterm.