CST370 Design and Analysis of Algorthms Week 5

For week 3 of CST370 Design and Analysis of Algorithms we learn about quick sort. Quick sort was first proposed by C.A.R Hoare in 1962. It uses Divide-and-Conquer and very popular but its efficiency can be tricky. Basically quicksort an n-element array it "Divides", in partition, the array into two subarrays around a pivot such that elements in the lower subarray elements in upper subarray. It then concquer recursively sort the two subarrays and combine. Quicksort worst case scenario when the data is already sorted and its has O(n^2) at its worst. Best case however it has O(nlogn) and its average case and use has that efficiency.

 We also learn this week about Binary tree traversals. A binary tree is a divide and conquer ready data structure. One classic problem with binary trees is to systematically visit each node. There are three binary tree traversals called inorder, preoder and postorder. Preorder, from the word "Pre", traversal visites the node in the order Root->Left->Right meaning Root is the first. Inorder, from the word "In", traversal visits the node in the order Left->Root->Right meaning the root is "In" the middle. Lastly, postorder, from the word "Post", traversal visits the node in the order of  Left->Right->Root meaning the root is at the last.

We also learn about decrease and conquer. The basic idea of this is that an algorithm design technique built on the idea that problems with smaller sizes are often easier to solve. It reduce a problem's instance to a smaller instance of the same problem then solve the smaller instance. Extend the solution of the smaller instance to obtain the solution to the original instance. There are three approaches in decrease-and-conquer. First is the decrease by a constant, generally we reduce the size of the problem by one for example a Topological sorting. Decrease by a constant factor, we reduce the size of the problem by half for example Binary search. Lastly, variable size decrease which the size of the problem we are reducing varies for example search and insertion in a binary search tree.

 Binary search  tree is a great example of decreasing by a constant factor. We generally reduce the size ofthe problem by half. The important thing about the algorithm is that the number of elements in the list is reduce by half each time. For example when searching a list of elements with a given key, binary search prerequisite is have the list of elements must be sorted. The basic operations are compare the middle element with the key and reduce the size in half if further comparison is needed. The time complexity of this algorithm is O(Log(n)) which is quite efficient.

 This week we also learn about DAG and Topological sorting. DAG or also known as Directed Acyclic Graph is a directed graph with no cycles. A topological Sort is ordered list with dependencies. Topological sorting has DFS as its based algorithm. Perform DFS traversal, noting the order in which vertices are popped off the traversal stack. Reverse order solves the topological sorting problem. If back edges encountered then that means it is NOT a DAG. Kahn's algorithm finds a topological order using the source removal approach. It repeatedly identifies and removes a vertex with no incoming edges. Its basic operations are to calculate the "in-degree" of each vertex and push the vertices with a"in-degree" zero into a queue. We then remove a vertex from the queue which decrease the "in-dgree" by 1 for its neighboring vertices and if the "in-dgree" of a neghboring vertex is reduced to zero, add the vertex to queue. All these steps are then repeated until queue is empty.