This week covered a lot more ground than last week. We finished divide-and-conquer with quicksort and binary tree traversal and height calculations, then moved on to two new design techniques: decrease-and-conquer and transform-and-conquer.
Divide-and-conquer
Quicksort
Quicksort does most of its work in the divide step. It picks a pivot and partitions the array so that everything less than or equal to the pivot is on its left and everything greater than or equal to it is on its right. The pivot is then in its final position, and the two sides are sorted recursively. No combine step is needed.
The efficiency depends on how even the splits are. If the pivot lands in the middle each time, the recurrence has the same form as merge sort, giving Θ(n log n). In class we used the first element as the pivot, which makes the worst case an already sorted array: the pivot is always the smallest element, so one side is empty and the other has n − 1 elements, giving Θ(n²). Median-of-three partitioning avoids this for sorted input by using the median of the first, middle, and last elements as the pivot. The average case is Θ(n log n), and quicksort sorts in place, unlike merge sort.
Binary trees
A binary tree is either empty or a root with a left and a right subtree, which are themselves binary trees, so it fits the divide-and-conquer paradigm. The height is found by computing the heights of the left and right subtrees, taking the larger one, and adding 1 for the root. The height of the empty tree is defined as −1, so a tree with a single node has height 0. The three traversals differ only in when the root is visited:
- Preorder: root, left, right
- Inorder: left, root, right
- Postorder: left, right, root
Each of these visits every node once, so they are all Θ(n). The height calculation also visits every node once, so it is Θ(n) as well.
Decrease-and-conquer
Decrease-and-conquer reduces a problem to a single smaller instance of itself, solves that, and then builds on that solution to solve the original problem. Divide-and-conquer, by contrast, solves several subproblems and combines their solutions.
Insertion sort decreases by one. Assuming the first n − 1 elements are already sorted, it inserts the last element by shifting larger elements to the right until it finds the correct spot. The worst case is a reverse-sorted array, Θ(n²). The best case is a sorted array, Θ(n), which is the opposite of quicksort with a first-element pivot. This makes it a good choice for nearly sorted input.
Kahn’s algorithm finds a topological order of a directed acyclic graph (DAG): an ordering of the vertices in which every edge points from an earlier vertex to a later one. A common example is ordering courses by their prerequisites. The algorithm is:
- Compute the in-degree of every vertex
- Put the vertices with in-degree 0 in a queue
- Remove a vertex from the queue, output it, and decrement the in-degree of each vertex it has an edge to
- Add any neighbor whose in-degree drops to 0, and repeat
Each step removes one vertex, leaving a smaller graph. If the queue empties before every vertex has been output, the graph has a cycle and no topological order exists. With an adjacency list, the running time is Θ(V + E).
Transform-and-conquer
Transform-and-conquer changes the problem into a form that is easier to solve. Presorting is the simplest example. Checking whether an array has duplicates by brute force compares every pair, Θ(n²). If we sort first with a Θ(n log n) algorithm like merge sort, any duplicates are adjacent, and one Θ(n) pass finds them. The sort dominates, so the total is Θ(n log n). The same idea works for finding the mode. This is why efficient sorting matters so much: many other problems get easier once the data is sorted.