[TOC]

Goal: classify problems according to computational requirements.

bad new: for huge number of pbs we don't know...

# 1. Introduction to Reductions

shifing gears:

- 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 ?

def. reduction

Pb Xreduces topb 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

(注意这次是反向的! )

pf.

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)?

### summary

#### 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

## Disqus 留言