CST370 - Module 7

What did I learn in the seventh week of CST370? 

This week introduced non-comparison sorting at the beginning of the module, which went over counting sort and radix sort. Basically, counting sort relies on frequency arrays rather than direct comparisons, producing a much more efficient way in finding the final results. On the other hand, radix sort applies stable sorting across each digit, which somewhat takes time in order to get the final answers depending on the numbers or digits inputted at the very beginning.

The module then shifted into dynamic programming, demanding a more structured way in solving problems through subproblems. Basically, dynamic programming introduced how to break problems down into overlapping subproblems and then compile the results, which was then supported through two different exercises that are called coin-collecting and coin-row, showcasing how one can solve something through clear recurrence with efficiency. We then moved onto graph algorithms that also relied on dynamic programming principles like the Warshall algorithm and Floyd algorithm with the former being about transitive closure and the latter being about all-pairs being done though the shortest path, having us work through matrix updates in each example.

The module then ended with the greedy technique and Prim's algorithm for constructing minimum spanning trees. Basically, the greedy technique is about choosing the best local option always, while the Prim's algorithm emphasized how important it is to track each visited vertex in order to select the smallest connecting edge with each step. In the end, this week covered a wide range of different strategies that have different methodologies and applications in real world structures, while providing examples that fully encompassed their core implementation or application for us to understand how each technique can be applied affectively.