Week 7 Learning journal- CST370

This week I learned about non-comparison sorting, dynamic programming, graph algorithms, and the greedy technique. We started with Counting Sort and Radix Sort, which sort without comparing elements. Counting Sort uses frequency and distribution tables to place elements directly, running in O(n + k) time. Radix Sort applies Counting Sort digit by digit starting from the least significant digit, running in O(d(n + k)) time, which is often linear.

This week focused on dynamic programming. I learned that the core idea is to solve overlapping subproblems once and store results in a table to avoid redundant work. We went through the Fibonacci sequence example, then the coin-row problem where you pick non-adjacent coins for maximum value, and the coin-collecting problem where a robot moves right or down on a grid to collect the most coins. I ended up implementing the coin-collecting problem for HW6-1 using the recurrence F(i,j) = max{F(i-1,j), F(i,j-1)} + c_ij, which helped me understand how DP works with 2D tables. We also covered Warshall's algorithm for transitive closure and Floyd's algorithm for all-pairs shortest paths. Both follow a similar structure of iteratively adding intermediate vertices and run in O(n^3).

Lastly, I learned about the greedy technique through Prim's algorithm, which builds a minimum spanning tree by always attaching the nearest vertex not yet in the tree.