CST370 - Week 7

 

CST370-30_2252: Design & Analysis of Algorithms – Week 7

In this module, we discuss the non-comparing sorting techniques, Counting sort, and Radix sort. In the counting sort, we use a range of values to calculate the frequency of the values, and then the sum of these frequencies is used to present the distribution. In the Radix, numbers are sorted by applying the counting sort for each digit, starting with the least significant digit. Unlike counting sort, Radix does not require a range of values and runs for the number of digits with time efficiency equal to O(d*(n + k)), where d is the number of digits.

Additionally, the lecture explored the use case of Dynamic programming as a design approach to solve problems with overlapping subproblems. For example, an algorithm that implements a solution to calculate the Fibonacci numbers uses a recursive function to repeatedly call functions for calculation. Applying dynamic programming to store the results from previously called functions in an array to avoid resolving a problem that has already been resolved once.

The coin collection problem is an example of an applied dynamic programming strategy to find an optimal path. The problem is modeled by a robot path with restricted movement to the right or down over a board of cells m x n. The solution highlights the principle of optimality for an algorithm that maximizes the collection of coins in a restricted path. Furthermore, we reviewed the coin-row problem, which calculates the maximum values of coins collected in a row. The constraint of this problem is that we are not allowed to pick up two adjacent coins.

Warshall’s algorithm provides a method of the traverse that determines the reachability of a i^th vertex from the j^th vertex, forming a transitive closure matrix of the digraph. The main idea of the algorithm is to obtain information on the existing path from the row i^th  vertex vi to the j^th vertex v_j, We use a matrix R(k) and immediate predecessor R(k−1) to mark the value 1 for exiting path. Similarly, Floyd’s algorithm for all-pairs shortest paths problem utilizes the same approach as Warshall’s. We can calculate the distance for n vertices in the nxn adjacency matrix for undirected and directed weighted graphs. The calculation is completed for each vertex to reach the final solution all pairs shortest path.

Finally, the module explains the Greedy technique to reach an approximate optimal solution. The logarithm finds the local optimal decision (greedy) for each step while adhering to any constraints. Once a step is performed, it cannot be changed until all steps are taken, yielding the final aggregated optimal solution. The minimum spanning tree (MST) utilizes the greedy concept in Prim’s algorithm to find the smallest weight of an undirected connected graph.