CST370 Module Five

 

CST370 Module Five

Quick Sort, Binary Tree, Decrease-and-Conquer, Transform-and-Conquer and Kahn's Algorithm

What I learned this week:

So this week covered a lot of different algorithm techniques centered around sorting, and graph traversal. the first we covered was the Quicksort algorithm in which we also learned about partitioning and how it can act as an alternative to merge sort in some cases. Although there are many different ways to partition, we worked around partitioning using a pivot point and two indices, the two indices essentially would start on either end and evaluate between the pivot and the left and right indices of the array, if ever an instance the two indices were out of order, we would initiate a swap between the two, and continue until the entire array was sorted.

We also covered the three different types of traversal of a Binary tree:

• Preorder traversal
• Inorder traversal
• Postorder traversal

We also covered a new method to approaching problems via Decrease-and-Conquer of which are three types used

• Decrease by a Constant,
• Decrease by a Constant Factor,
• Variable Size Decrease, of which binary Search would be categorized under this type.

We also covered Topological Sorting and a few other terms such as Directed Acyclic Graphs which describe a graph with no back edges.