Learning Journal

Dynamic Programming:  Dynamic programming is a technique used to solve problems by breaking them into smaller overlapping subproblems and storing their solutions to avoid repeated work. It relies on two main ideas:  overlapping subproblems  and  optimal substructure . I am trying to focus more on identifying when a problem should use dynamic programming instead of other techniques like divide and conquer.  Warshall's Algorithm: Warshall’s algorithm is used to compute the  transitive closure of a graph , meaning it determines which vertices are reachable from others. It works by systematically updating a matrix representation of the graph, checking whether a path exists through intermediate vertices. I find it confusing  how the matrix updates guarantee that all indirect paths are eventually captured , especially when multiple intermediate nodes are involved. Floyd's Algorithm: Floyd’s algorithm is used to find the  shortest paths between all pairs...

 AVL Trees:  AVL trees are a type of  self-balancing binary search tree  where the height difference (balance factor) between the left and right subtrees of any node is at most 1. When this balance is violated,  rotations  (left, right, left-right, right-left) are performed to restore balance. This ensures that operations like search, insertion, and deletion remain efficient at  O(log n) . Questions: It is still difficult to determine which rotation (single vs. double) to apply in different imbalance cases. The conditions have many similarities which makes it difficult to differentiate.  2-3 Trees:  A 2–3 tree is a balanced search tree where each node can have either  two children (2-node)  or  three children (3-node) . Values are stored in a way that maintains sorted order, and the tree remains balanced by splitting nodes when they become too full. This guarantees that all leaves are at the same depth. Heaps and Heapsort:...

Quicksort: Algorithm that sorts an array by selecting a pivot element and partitioning the remaining elements into two subarrays: those less than the pivot and those greater than it. The algorithm then recursively sorts the subarrays.  Binary Tree Traversal and Height: Tree traversal refers to the systematic way of visiting all nodes in a binary tree, and the three main depth-first traversal methods are preorder, in order, and postorder. Each traversal follows a different order of visiting the root and its subtrees, which affects how the tree’s data is processed. I also learned that the height of a binary tree is defined as the length of the longest path from the root to a leaf, which directly impacts the efficiency of operations like searching or inserting in certain tree structures.  Introduction to Decrease-and-Conquer: A fundamental algorithm design technique where a problem is solved by reducing it to one smaller instance of the same problem and then extending that soluti...