Week 5 Learning journal- CST370

This week's module focused on the practical application of the Divide and Conquer strategy through Quicksort and the logic of dependency management using Topological Sorting. Quicksort is an efficient, in-place sorting algorithm, which means it sorts the input array without requiring significant additional storage. A key component of its performance is the partitioning process, where a pivot is selected to split the array into two subarrays. I learned that using a Median-of-Three pivot selection is a common technique to avoid the worst-case time complexity of O(n^2) that occurs when the input is already sorted.

The study of graph algorithms introduced Topological Sorting specifically for Directed Acyclic Graphs (DAGs). Using Kahn's Algorithm, I explored how to order vertices linearly based on their in-degrees. This process involves identifying vertices with an in-degree of zero, adding them to a queue, and then updating the in-degrees of their neighbors as they are processed. This algorithm is essential for solving problems related to task scheduling and prerequisite management, where certain operations must be completed before others can begin.

I applied these concepts in the homework assignments for this week. In HW4_1, I implemented a program to compare the performance of Quicksort and Insertion Sort. This exercise demonstrated how Quicksort's average-case O(n \log n) complexity provides a significant performance advantage over the O(n^2) complexity of Insertion Sort as the size of the data increases. Managing the left and right indices during the partitioning step was a critical part of ensuring the implementation matched the required pseudocode.

For HW4_2, I used Kahn's Algorithm to perform a topological sort on a user-provided graph. A specific requirement of this task was to process adjacent vertices in numerical ascending order, which required careful management of the adjacency list. The assignment also reinforced how to detect if a graph is not a DAG; if the final sorted order does not contain all vertices, it indicates the presence of a cycle. Completing these implementation tasks helped solidify my understanding of the theoretical trade-offs between different algorithm designs.