CST 370 - Week 5 Learning Journal

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 solution. Unlike divide-and-conquer, which splits a problem into multiple parts, decrease-and-conquer works with a single reduced version. 

Binary Search: A clear example of the decrease-by-a-constant-factor approach because it reduces the problem size by half at each step. I learned that binary search requires the input to be sorted and works by repeatedly comparing the target value to the middle element of the list. If the value is not found, half of the remaining elements are eliminated from consideration. This leads to a time complexity of O(log n), which is much more efficient than linear search for large datasets. 

Introduction to DAG and Topological Sorting: They are used to represent relationships with dependencies. A DAG is a directed graph with no cycles, meaning there is no path that starts and ends at the same vertex following the direction of edges. Topological sorting provides an ordering of the vertices such that for every directed edge from one vertex to another, the first appears before the second in the ordering. 

Algorithm Design with Pre-Sorting: By sorting the input first, many problems become easier to solve, such as detecting duplicates or improving search efficiency. Although sorting itself takes O(n log n) time, it can reduce the complexity of later steps and make the overall algorithm more efficient.