Week 7 Dynamic programming and Greedy techniques
This week in Design and Analysis of Algorithms we took a look at two sorting algorithms known as count sort and radix sort, we unraveled Dynamic Programming by analyzing two coin related problems such as the robot coin collection and coin row problem. In addition we explored transitive closure with Warshall's algorithm and found the shortest path of pairs of vertices with Floyd's algorithm which coincidentally utilizes Warshall's Algorithm. And lastly this week we looked at greedy techniques by finding Minimum spanning trees utilizing Prim's algorithm. The sorting algorithms this week were quite interesting because they didn't utilize comparisons like those that we learned in the previous weeks. The counting algorithm rather utilizes a table to construct the sorting of an array of integers. The table that must be created is a frequency distribution table and essentially it contains the range of the input values, the frequency or the amount of times that input value ...