Cohort 23 CS Online Journal

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 alg...

CST370 Week 6 This week, we learned more about tree balancing and hashing.      AVL trees are self-balancing binary search trees where the balancing factor of each node is either 1 (left), 0, or -1 (right). The balancing factor is calculated by how many 'edges' traveled from the node to the last leaf it can reach (or the height of the subtree): Balancing factor = height of left subtree - height of right subtree      To maintain AVL trees, rotations may need to be made on nodes. For left-heavy trees (or subtrees), R-rotations are typically used, while right-heavy trees (or subtrees) use L-rotations. Rotations can be used multiple times in a row, like two R-rotations needed.      2-3 trees are binary search trees that must have at least 2 or 3 children to each node. Each node can contain one value or two values - if it has one value, it will have 2 children, and if it has two values, it will have 3 children. The children can contain one or two ...