- 1. Introduction to Reductions
- 2. Designing Algorithms
- 3. Establishing Lower Bounds
- 4. Classifying Problems
Goal: classify problems according to computational requirements.
bad new: for huge number of pbs we don't know...
1. Introduction to Reductions
- from individual problems to problem-solving models.
- from linear/quard to polynomial/exponential pbs
- from implementation details to conceptual framwork
suppose we could (not) solve pb X efficiently
⇒ what else pbs could (not) we solve efficiently ?
Pb X reduces to pb Y if you can use an algo that solves Y to solve X.
for an instance of pb X → transform it into an instance of pb Y → translate the solution for Y to solution for X.
ex1. finding median can reduce to sorting... cost = NlogN+1
ex1. element distinctness can reduce to sorting... cost = NlogN + N
2. Designing Algorithms
algo design: by reduction to problems that we know how to solve (sorting/shortest path/flow/...)
ex1. convex hull reduces to sorting
Gram scan algo... (discussed in algo-I course)
cost = NlogN + N
algo. Gram scan
- pick a point with smallest y-coord
- sort all points by polar angle wrt the picked point
- consider points in this order, discard points that creates clockwise turn
ex2. undirected shortest path (nonneg weights) reduces to directed shortest path
cost: ElogV + E
algo. replace each undir-edge by 2 dir-edge...
3. Establishing Lower Bounds
goal: prove that a pb requires (at least) a certain nb of steps.
ex. any compare-based sorting requires NlogN compares. log(N!) = NlogN
Bad news: very hard to estibalish lower bounds.
Good new: can spread the lower bound NlogN by reducing to sorting (if cost of reduction is small).
def. linear-time reduction
pb X linear-time reduces to pb Y if X can be solved with:
1. linear nb of op for reduction
2. constant nb of calles to Y
ex. almost all reductions we've seen so far...
ex. proof of lower bound for convex hull
prop. sorting linear-time reduces to convex hull
for an instance of sorting: x1 ... xn
⇒ convert to convex hull instance: (x1, x1^2), ... , (xn, xn^2)
⇒ implication: all (ccw-based) convex hull algo cannot be easier than NlgN ! (otherwise sorting would be easier..)
lesson: Establishing lower bounds through reduction is an important tool in guiding algorithm design efforts.
4. Classifying Problems
prove that pb X and pb Y have the same complexity:
- show X linear-time reduces to Y
- show Y linear-time reduces to X
- conclude that X Y have the same complexity (even if we don't know what it is)
ex. sorting and convex hull...
ex. integer arithmetic reductions: integer multiplication
integer multiplication: of two N-bit integers.
Its complexity (unknown) is denoted as M(N)
brute force: N^2 ops → so M(N) = Omega(N2)
many other integer ops can reduce to integer multiplication:
what is M(N)?
ex. linear-algebra reductions: matrix multiplication
compute product of 2 N*N matrices.
Its complexity (unknown) is denoted as MM(N)
brute force: N^3
operations that can reduce to matrix-multiplication:
what is MM(N)?
Part 11 of series «Algorithms Princeton MOOC II»：
- [Algorithms II] Week 1-1 Undirected Graphs
- [Algorithms II] Week 1-2 Directed Graphs
- [Algorithms II] Week 2-1 Minimum Spanning Trees
- [Algorithms II] Week 2-2 Shortest Paths
- [Algorithms II] Week 3-1 Maximum Flow
- [Algorithms II] Week 3-2 Radix Sorts
- [Algorithms II] Week 4-1 Tries
- [Algorithms II] Week 4-2 Substring Search
- [Algorithms II] Week 5-1 Regular Expressions
- [Algorithms II] Week 5-2 Data Compression
- [Algorithms II] Week 6-1 Reductions
- [Algorithms II] Week 6-2 Linear Programming
- [Algorithms II] Week 6-3 Intractability