Reference
Introduction
A problem L that is NP-hard; assume that P≠NP, we can’t have an algo A for L s.t.
- A has polynomial runtime
- A is deterministic [counter: randomized algo]
- A is exact [counter: approxiamtion algo]
- A solves every instance of L [counter: parameterized algo]
1 Amortized Analysis
Amortized Analysis
2 Randomized Algorithms
Randomized Algorithms
3 Parameterized and Exponential-Time Algorithms
Parameterized Algorithms
4 Approximation Algorithms
5 Population Protocols
6 Streaming Algorithms