CST 370

  Weekly Learning Journal: Week 7 Reflection Technical Focus: Breaking the O mega(n log n)  Barrier This week’s module centered on a pivotal shift in algorithmic strategy: the transition from comparison-based sorting to Non-Comparison Sorting techniques like Counting Sort and Radix Sort . In previous modules, we established that comparison-based algorithms (like Merge Sort or Quick Sort) are mathematically bounded by a lower limit of \Omega(n \log n)$ . However, I learned that by making specific assumptions about the input data—such as the range of integers or the number of digits—we can achieve Linear Time Complexity O(n) . While the time efficiency is superior, the trade-off lies in Space Complexity , as these algorithms require auxiliary arrays or "buckets" to track frequencies or digit distributions. Strategic Transitions: Greedy vs. Dynamic Programming Furthermore, we began exploring the Greedy Technique through Prim’s Algorithm for finding the Minimum Spanning Tree ...

  Week 6 Learning Journal: Heaps and Hashing This week’s module focused on advanced data structures, specifically Heaps and Hash Tables, which are essential for optimizing search and priority-based operations. Heaps and Priority Queues I learned about the Max Heap property, where every parent node must be greater than or equal to its children. This structure is particularly efficient for implementing Priority Queues. One of the most interesting takeaways was the $O(n)$ bottom-up heap construction algorithm. Unlike inserting elements one by one ( $O(n \log n)$ ), the bottom-up approach starts from the last non-leaf node and "heapifies" down, which is mathematically more efficient. I also practiced the mechanics of insert and deleteMax . When deleting the root, we replace it with the last element and percolate it down to maintain the heap property. This ensures that the highest priority element is always accessible at the root in $O(1)$ time. Hashing and Collision Resolution...

  Week 5 Learning Journal: Advanced Algorithm Analysis and Graph Theory During Week 5, my studies centered on the refinement of sorting techniques and the practical application of graph theory. A major focus was the Master Theorem , which provides a streamlined "cookbook" method for determining the asymptotic bounds of recurrence relations. Applying this to Divide and Conquer algorithms like Merge Sort and QuickSort helped me visualize how the number of subproblems ( a ) and the size of those subproblems ( n/b ) directly dictate the overall time complexity. I also spent significant time on Decrease-and-Conquer algorithms. While Divide and Conquer breaks a problem into multiple subproblems, Decrease-and-Conquer reduces a problem to a single, smaller instance. A prime example I studied was Binary Search . Understanding its O(log n)  efficiency is vital, but I also learned about its application in Topological Sorting . I specifically focused on Kahn’s Algorithm , which uses a q...

  Week 4 Learning Journal: Merge Sort, The Master Theorem, and Midterm Synthesis Technical Summary: Week 4 was a pivotal point in CST 370 as we transitioned from basic brute-force techniques to the Divide-and-Conquer paradigm. The primary focus was Merge Sort , a sophisticated sorting algorithm that employs a recursive strategy to achieve $O(n \log n)$ efficiency. The logic involves two distinct phases: the "Divide" phase, where the array is split into $n$ sub-lists (each containing one element), and the "Merge" phase, where those sub-lists are repeatedly merged to produce new sorted sub-lists until only one remains. A major highlight of this week was applying the Master Theorem to analyze algorithm efficiency. The Master Theorem provides a mechanical way to solve recurrence relations of the form T(n) = aT(n/b) + f(n) . For Merge Sort, the relation is T(n) = 2T(n/2) + \Theta(n) . Since the work done at each level of the recursion ( f(n) ) matches the cost of the...