CST 370 - Week 5

 Hey everyone!

This week, I explored several important algorithm design techniques and deepened my understanding of how they are applied in solving complex problems efficiently.

One of the key highlights was learning about Quick Sort, a widely used sorting algorithm that relies on the Divide-and-Conquer strategy. I now understand how Quick Sort works by dividing the array into smaller parts around a pivot, sorting those parts recursively, and then combining the results. I also learned about its efficiency and how its performance depends on the choice of the pivot.

I also studied Binary Tree traversal methods, such as inorder, preorder, and postorder, and how each serves a specific purpose when working with hierarchical data. Alongside traversal, I learned how to calculate the height of a binary tree, which is a foundational concept for evaluating the balance and efficiency of tree-based data structures. I even added my insights on the class Discord group, explaining an easy calculation method for the height of a binary tree.

A new design technique introduced this week was Decrease-and-Conquer, which involves reducing a problem to a smaller instance of itself and solving the smaller instance first. I explored how Insertion Sort is an example of this approach, and I was able to compare how it differs from Divide-and-Conquer in both concept and application.

Another interesting topic was Topological Sorting for directed graphs, which is especially useful when scheduling tasks that have dependencies. I learned how Kahn’s algorithm implements a Decrease-and-Conquer approach by repeatedly removing nodes with no incoming edges and building the sorted order step by step.

Lastly, I was introduced to Transform-and-Conquer, a technique where a problem is first transformed into a different form that is easier to solve. An example of this is pre-sorting, where sorting the data first makes certain problems simpler or more efficient to solve.

Overall, this week has given me a better grasp of not just specific algorithms, but also the broader design techniques that guide how algorithms are constructed and applied. I’m beginning to see how these strategies can be chosen based on the nature of the problem and the structure of the data.