Syllabus
Detailed information about the course are given at the web page https://kam.mff.cuni.cz/~kolman/intapxalg.html .
Here is a list of the main topics.
Covered techniques:
- Greedy algorithms as a design method for approximation and online algorithms
- Use of linear programming for approximation algorithms
- Pairwise independent random variables
- Derandomization using the conditional expectations technique
- Local search
Covered problems and algorithms:
- scheduling and disjoint paths in graphs - greedy algorithms
- travelling salesperson problem - combinatorial algorithms
- set cover - greedy algorithm, use of linear programming
- satisfiability (MAX-SAT) - use of linear programming, randomized rounding, derandomization
- dynamic and static hashing - randomized algorithms, pairwise independent variables
- maximal cut - approximation using local search
- minimal cut - a fast randomized algorithm
- maximal independent set - a fast randomized parallel algorithm
- verification of matrix equation - a randomized protocol
Annotation
This course covers techniques for design and analysis of algorithms, demonstrated on concrete combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design algorithms that find an optimal solution fast. In such a case we study approximation algorithms that work faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness in design of algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable.
Recommended for the 3rd year of Bc. studies.