Algorithms and Complexity

* Approximation algorithms

- The NPO, APX, PTAS, FPTAS complexity classes
- Greedy techniques
... The load balancing problem [A]
... The center selection problem [A]
... Inapproximability of the center selection problem [C]
... The set cover problem [A]
- Pricing technique
... The vertex cover probem [A]
... The disjoint paths problem [A]
- Rounding techniques
... Vertex cover by rounding [A]
- Other examples
... The Christofides algorithm for metric TSP [B]
... Inapproximability of TSP [D.6]
- Polynomial time and fully polynomial time approximation schemes
... A PTAS (based on the reduced exhaustive solution) of the minimum partition problem [G]
... A FPTAS (based on rounding) of the knapsack problem [C]

- Probabilistic algorithms

- The Karger algorithm for minimum global cut [E]
- The Miller-Rabin for primality (no proof) [H]
- A randomized-rounding algorithm for set cover [D.4]
- A probabilistic algorithm for MaxEkSat and its derandomization [D.3]
- Approximation complexity

- The PCP theorem (no proof) [F.3, Theorem 1]
- PCP and inapproximability of MaxSat and MaxE3Sat [F.3.1]
- PCP and inapproximability of independent set [F.4.4, Claim 13 and Claim 14]

- Succinct, quasi-succinct and compact data structures

- Succinct structures for rank and selection; the "Four-Russians Trick" [D.9, excluding 9.2]
- Succinct structures for binary trees [D.10]
- Quasi-succinct Elias-Fano coding for monotone sequences [D.11, excluding D.11.1 and D.11.2]
- Compact structure for balanced parenthesis [D.12]
- Quasi-succinct functions: the MWHC technique [D.13]
- Minimal perfect hashing [D.13]