Week 4 Learning Journal- CST370

This week focused on the core mechanics of algorithm design, specifically the differences between Divide and Conquer and Decrease and Conquer. One of the most important takeaways for me was breaking down QuickSort. While I knew it was a popular sorting method, I didn't fully appreciate how much the "pivot" choice matters. The fact that it's an in-place algorithm is a huge advantage over Merge Sort because it doesn't require extra memory, but the trade-off is that a bad pivot choice can tank the performance from a fast O(n log n) down to a slow O(n^2). Seeing the partitioning process step by step made it much easier to understand how the elements are actually swapped around the pivot to get them into the right spots.

I also spent time looking at Binary Tree Traversals. It was helpful to see how Pre-order, In-order, and Post-order aren't just different ways to list nodes, but tools for different problems. For example, I realized that Post-order traversal is the most logical choice when you need to calculate the height of a tree because you need to know the status of the "children" nodes before you can say anything about the "parent" node. It’s a very clear application of recursive logic where you solve the subproblems first to get your final answer.

The introduction to Decrease and Conquer provided a different perspective on problem-solving. Unlike Divide and Conquer, which splits a problem into multiple subproblems, Decrease and Conquer reduces a problem to a single, smaller instance. I really liked the application of this in Topological Sorting for Directed Acyclic Graphs (DAGs). Using the source removal method where you find a node with no dependencies, remove it, and repeat makes a lot of sense for real-world scenarios like planning out course prerequisites. It basically mirrors how we tackle a complex project by finding the one thing we can actually start on and moving forward from there.