CST 370 - WEEK 5

This week, we dug deeper into quicksort, focusing especially on how partitioning works and why it’s so essential to the algorithm. We also learned the Median‑of‑Three Partitioning method, where the pivot is chosen by taking the median of the first, middle, and last elements. After arranging those three values in ascending order, the algorithm proceeds with partitioning as usual. Seeing how this improves performance on certain inputs helped me understand why pivot selection matters.

We also reviewed the different ways to traverse a binary tree: In‑Order (Left, Root, Right), Pre‑Order (Root, Left, Right), Post‑Order (Left, Right, Root)

It was helpful to see how each traversal reveals different structural information about the tree.

Beyond quicksort, we explored more sorting and problem‑solving strategies, especially Decrease and Conquer. The idea is to reduce a problem to a smaller instance, solve that smaller instance, and then extend the solution back to the original problem (ex: topological sorting). Using Kahn’s algorithm, we calculate the in‑degree of each vertex, push all vertices with in‑degree zero into a queue, remove them one by one, decrease the in‑degree of their neighbors, and add any neighbor whose in‑degree becomes zero. Seeing this process in action made the logic behind topological ordering much clearer.

I also spent time watching the videos posted in our Slack channel to strengthen my understanding of time complexity, since that was the area I struggled with most on the midterm. I’m hoping that with more practice and review, I’ll feel much more confident by the time the final comes around.