This week, we were introduced to the Quicksort algorithm, which is an efficient sorting technique based on the divide-and-conquer strategy. It works by selecting a pivot element from an array and then partitioning the remaining elements into two subarrays, one containing elements less than the pivot and the other containing elements greater than the pivot.
Additionally, we covered binary tree traversals and how to calculate the height of a binary tree. We also learned about the decrease-and-conquer technique, which involves reducing a problem to a smaller instance of the same problem and applying the solution recursively. An example of this is binary search, where the list is reduced by half at each step.
Lastly, we explored topological sorting using Directed Acyclic Graphs (DAGs) and Kahn's Algorithm, which relies on tracking the in-degree of each vertex and a queue. The in-degree represents the number of edges directed into a vertex. For instance, if vertex C has edges directed at it from vertices B and D, its in-degree is 2.
In the programming homework, we implemented topological sorting using Kahn's Algorithm, as well as calculated the height of a binary tree. Overall, I felt that my understanding of this week's material was strong.
No comments:
Post a Comment