- stable Matching problem
- knapsack
- subset sum
- segmentation
- sequence comparison
- IMPL: sequence alignment
- segmented least squares
- median finding (randomized divide-and-conquer)
- counting inversions
- finding the closest pair of points
- integer multiplication
- vertex cover
- independent set
- packing problem
- covering problem
- satisfiability problem
- circuit satisfiability problem
- traveling salesman
- hamiltonian cycle
- hamiltonian path
- partitioning problem
- 3-dimensional-matching
- graph coloring
- bipartite matching
- s-t connectivity