Description
| 1. Mathematical background
1.1 Asymptotic growth rate of functions
1.2 Solving recurrence relations
1.3 Mathematical induction
2. Basic analysis techniques
2.1 Computational complexities -- lower bounds and upper bounds
2.2 Worst case analysis and average case analysis
2.3 Amortized analysis
3. Basic Design Paradigms
3.1 Divide and conquer
3.2 Greedy methods
3.3 Dynamic programming
3.4 Probabilistic algorithms
4. Computational Complexity
4.1 Information-theoretic arguments
4.2 Adversary arguments
4.3 Linear reduction of problems
4.4 NP-completeness
|
---|