CST370 - Week 7

CST370 Week 7 (& 8?)

    This week we learned about dynamic programming and how to use backtracking to find optimal solution paths. Instead of brute-forcing through all solution paths, dynamic programming uses a solution array that keeps track of already-calculated sub-problems in a table. Once we hit the end, we can use that table to backtrack and find the solution to the problem.

    We also learned about Warshall's algorithm, which uses transitive closure to find paths from one vertex to a non-adjacent vertex in a directed graph, and Floyd's algorithm to further apply this to find the all-pairs shortest-paths matrix solution of a connected cyclic graph. The solution to Warshall's algorithm is a matrix of 0s and 1s showing if a valid path from one vertex to another is possible. If the path (row) has all 1s across, a path from that vertex (row index) can be traced to all vertices, including itself if it is part of a cycle. The solution to Floyd's algorithm is a completed matrix with no infinity values that shows the shortest path to each vertex.

    The final topic is the greedy technique and applying it to Prim's algorithm. Greedy technique solves problems through a series of choices that must satisfy the problem's constraints, be locally optimal, and is irrevocable. We apply this to Prim's algorithm by constructing a minimum spanning tree for a given connected graph, starting at a given vertex: T1, T2, T3, ... Ti. We add T(i+1) from the shortest (closest) vertex that is not in Ti, until all vertices are added to the tree. The step to add the closest vertex not in Ti is a greedy step.

Isopod Update: There's a lot of babies!