Week 64: CST370 - Design and Analysis of Algorithms

 WK05: Weekly Reflection

This week's module focused on Quick Sort, binary tree traversal and height calculation, decrease-and-conquer algorithms, topological sorting, and transform-and-conquer through pre-sorting. These topics helped me understand how different algorithm design techniques can simplify problems and improve efficiency.

One topic that stood out to me was Quick Sort. I learned that Quick Sort is based on the divide-and-conquer technique. It selects a pivot, partitions the remaining elements into smaller and larger groups, and then recursively sorts those groups. The median-of-three partitioning method was also useful because it showed how choosing a better pivot can improve the performance of the algorithm. The exercises helped me understand how partitioning works step by step and why pivot selection can affect efficiency.

The binary tree materials were also helpful. I learned about different traversal methods, including preorder, inorder, and postorder traversal. Each method visits the nodes in a different order depending on when the root node is processed. I also learned how to calculate the height of a binary tree recursively. These topics showed me how recursion can be used to process hierarchical data in an organized way.

Another important topic was the decrease-and-conquer design technique. Unlike divide and conquer, which may divide a problem into several smaller subproblems, decrease and conquer usually reduces the problem to one smaller version, solves it, and then extends the solution. Insertion Sort was a clear example because it builds a sorted list by inserting one element at a time into the correct position. Binary Search also demonstrated this technique by repeatedly reducing the search area until the target is found or the search space becomes empty.

The lectures on directed acyclic graphs and topological sorting helped me understand another application of decrease and conquer. A topological order arranges the vertices of a directed graph so that each vertex appears before the vertices that depend on it. Kahn’s algorithm creates this order by repeatedly selecting vertices with an in-degree of zero and removing their outgoing edges. This showed me how a large graph problem can be solved gradually by reducing the graph one vertex at a time.

The transform-and-conquer materials introduced another useful strategy. I learned that this technique changes a problem into a form that is easier to solve. Pre-sorting is one example because sorting the data first can make later operations, such as searching or detecting repeated values, more efficient. Although sorting requires additional work at the beginning, it can simplify the rest of the problem and improve the overall solution.

Overall, this week helped me see how algorithm design techniques are connected. Quick Sort applies divide and conquer, while Insertion Sort, Binary Search, and Kahn’s algorithm use decrease and conquer. Pre-sorting demonstrates how transforming the input can make a problem easier to solve. My main takeaway is that selecting an appropriate design technique can make an algorithm more organized, efficient, and easier to understand.