CST370 - Week 5

 

CST370-30_2252: Design & Analysis of Algorithms – Week 5

Module 5 introduces Quicksort, another algorithm using the divide-and-conquer technique. Unlike mergesort, division is the primary stage for solving the problem, and not much work for combining subproblems. A pivot is used to partition an array with a value of elements smaller than the pivot to the right and a value of elements larger than the pivot to the left. We can define the best-case scenario, if an array splits in the middle for partitioning. On the contrary, the worst-case scenario occurs if one subarray yields empty – for example, an increasing array with the selected pivot at an index zero.

The decrease and conquer algorithm design technique utilizes three approaches: decrease by a constant, decrease by a constant factor, and variable size decrease. The textbook explains the concept by illustrating solving a^n where a > 0, and n is a nonnegative integer. The exponential problem could be resolved by decreasing by a constant 1 as follows a^n = a^n-1 * a. Applying the recursive function obtained from this relationship leads to the solution to

the original problem. The binary search is an example of a decrease by a constant factor since elements in a list is reduced by 50%. 

Binary Search Tree (BST) with root node 10

In this section, we applied the divide-and-conquer strategy to solve many problems that resemble a binary tree. The standard representation of a binary tree consists of the left subtree, the right subtree, and the root. Additionally, we reviewed the three types of binary tree traversals: preorder, inorder, and postorder.

We also discussed topological sorting for Directed Acyclic Graphs (DAGs). An important aspect of the Depth-First Search (DFS) forest is the absence of back edges, which is essential for topological sorting. In other words, it is necessary for the directed graph to be acyclic in order to resolve the topological sorting problem. Lastly, the module covered presorting to improve overall time complexity. For example, checking element uniqueness in a sorted array can enhance the algorithm's efficiency, reducing the complexity fromꝊ(n^2) to Ꝋ(n log n).