1. Divide the problem (instance) into subproblems. 2. Conquer the subproblems by solving them recursively. 3. Combine subproblem solutions

All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements

Symbol-table problem Symbol table T holding n records: key key[x] [x]

The depth of a node = the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have

Dynamic order statistics OS-SELECT(i, S): returns the ith smallest element in the dynamic set S. OS-RANK(x, S): returns the rank of x ∈ S in the sorted order of S’s elements. IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes

Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u – 1} of size u subject to these operations:

Dynamic programming Design technique, like divide-and-conquer. Example: Longest Common Subsequence (LCS)

Consider a digraph G = (V, E) with edge-weight function w : E → R. The weight of path p = v1 → v2 → L → vk is defined to be

Shortest paths Single-source shortest paths Nonnegative edge weights

Take-home quiz No notes (except this one)