Week 5 Sorting and Decrease and Conquer

This week in Design and Analysis of Algorithms, we took a look at the widely used sorting algorithm Quicksort, explored the different operations and efficiencies of algorithms involving the binary tree which included learning how to traverse the trees and determine the heights. In addition, we learned about the different decrease and conquer designed algorithms such as the insertion sort and the topological sorting of directed acyclic graphs by using DFS based algorithms, source removal, and Kahn's Algorithm. Lastly, we were introduced to another algorithmic design technique known as transform and conquer which involved the concept of pre-sorting.

From a short glimpse of the module I thought this week would be pretty hectic due to seeing all the different tabs and links, but overall I found it quite tame. At first glance the quick-sort algorithm seemed quite confusing with having to do the partitioning aspect of it. I had to visualize the way the partitioning was indexing the array's on paper because I kept getting lost on where the i and j index were currently at after the swaps. But after practicing and going through the module's document on quick sorting I found it a lot easier to manage and visualize in my head. The binary tree traversals also took a bit to get use to, such as the in-order which involves going from the left node -> root node -> right node, and the post-order which involved traversing through the left node -> right node -> root node. Again I had to visualize them on paper, so ultimately this week I definitely used a lot of scratch paper to go through all of the exercise problems. My biggest takeaway from this week was going through the topological sorting with DAGs or directed acyclic graphs, especially using the Kahn's algorithm. 

From the lecture Kahn's algorithm is involved by first finding the amount of in-degrees or incoming edges there are to a node, doing so for each node in the graph. We do this by putting them in a data structure to keep count of each vertices' in-degree. After getting the in-degrees, we select the nodes with in-degrees of value 0 and add them to a queue, ideally in alphabetical order. We then pop the vertices one by one, but for each vertices removed, if it had any outgoing edges to adjacent vertices, the in-degree's of those adjacent nodes will be taken out by decrementing the in-degree value, if the their in-degree hits 0 they are moved to the queue. It will continue to add and pop nodes of in-degree 0 until all vertices are gone from the queue which would mean that the graph was acyclic, and if there are still vertices in the queue then the graph may contain a cycle. The order in which the vertices were popped from the queue is the topological sorting. Overall I thought this algorithm was the most interesting this week, especially its involvement in part 2 of this week's homework. 

Lastly, I'll briefly mention the transform and conquer technique we were introduced to, which involves transforming a problem into a different form so that it is much easier to solve. An example from this week was the solving element uniqueness, in which brute forcing would have an efficiency of Big O(n^2), while on the hand initiating a pre-sorting based algorithm to transform then work through the problem creates a better efficiency of theta (n log n). I will say overall this week was very interesting and I felt a lot more engaged with the assignments similarly to week 3 with the DFS and BFS problems. Overall it was a good week! Here's to another week of Design and Analysis of Algorithms.