CST370 - Week 5

This week we took a deeper look into different algorithmic approaches to sorting. We started off learning about quick sort which partitions based on a pivot. We learned about binary trees and how they are a structure ready for use of the divide-and-conquer technique. Three ways to traverse binary trees are preorder, inorder, and postorder. Another approach to solving a problem is the decrease-and-conquer approach which reduces the problem to a smaller instance, solves that smaller instance, and then extends the solution. The problem can be decreased by a constant, decreased by a constant factor, or decreased by a variable size. This technique is implemented in the insertion sort algorithm. We then learned about the topological sorting of a directed acyclic graph and its implementation using an in-degree array and queue. Lastly, we discussed binary search and presorting.

We had 3 program assignments this week. The first instructed us to write a program that reads input values and puts all negative numbers before positive ones. The second required us to use the divide-and-conquer approach to display the biggest value in an array. Lastly, we wrote a program that conducted a topological sorting based on Kahn's algorithm.