Dynamic Programming

This week, I explored how Counting Sort and Radix Sort work without direct comparisons by grouping or distributing elements based on digit values. These methods helped me understand how certain sorts can achieve linear time when the range of data is limited. We also practiced dynamic programming. Dynamic Programming (DP) solves problems by breaking them into smaller overlapping problems. In the coin-row and coin-collecting examples, I used recurrence relations to build solutions to maximize path rewards. These exercises show how efficient DP is because it stores previous results to avoid redundant work. 

We also covered graph algorithms like Warshall’s, Floyd’s, and Prim’s. Warshall’s and Floyd’s algorithms rely on updating matrices to determine connectivity and shortest paths. Prim’s algorithm builds a minimum spanning tree by adding the smallest edges step by step. This module strengthened my understanding of dynamic programming and graph algorithms. These prove to be useful tools that use similar techniques of incremental computation to solve problems more efficiently.