Materials are available on the web page of the lecturer: https://www.cs.vsb.cz/sawa/ta
Consultations using MS Teams.
Theory of Algorithms
| Type of study | Follow-up Master |
|---|---|
| Language of instruction | Czech |
| Code | 460-4167/01 |
| Abbreviation | TA |
| Course title | Theory of Algorithms |
| Credits | 5 |
| Coordinating department | Department of Computer Science |
| Course coordinator | doc. Ing. Zdeněk Sawa, Ph.D. |
Subject syllabus
Lectures:
- Introduction. Algorithms and algorithmic problems. Models of computation (e.g., RAM machines, Turing machines, ...). Church-Turing thesis.
- Algorithmically undecidable problems.
- Computational complexity of algorithms. Asymptotic notation. Examples of techniques used in the analysis of computational complexity of algorithms. Analysis of computational complexity of recursive algorithms.
- Complexity classes. Nondeterministic algorithms. Classes P and NP. Reductions between problems. NP-completeness.
- Examples of some classical problems from the area of combinatorial optimization. Examples of problems where some of them are in P and some NP-complete.
- Some other complexity classes (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Examples of complete problems for these classes.
- Examples of techniques of design of efficient algorithms. Examples of use of these techniques for solving combinatorial problems.
Greedy algorithms and their relationship with matroids. Branch and bound method.
- Complexity of algorithms in an average case. Amortized complexity. Examples of some more advanced data structures and of analysis of complexity of operations on these structures.
- Randomized algorithms.
- Approximation algorithms. Hardness of approximation of some problems.
- Parallel algorithms: Model of computation for parallel algorithms (PRAM). Computational complexity of parallel algorithms.
- Distributed algorithms: Models of computation for distributed algorithms, communication complexity.
Tutorials:
- Algorithms and algorithmic problems. Models of computation (e.g., RAM machines, Turing machines, ...). Church-Turing thesis.
- Algorithmically undecidable problems.
- Computational complexity of algorithms. Asymptotic notation. Examples of techniques used in the analysis of computational complexity of algorithms. Analysis of computational complexity of recursive algorithms.
- Complexity classes. Nondeterministic algorithms. Classes P and NP. Reductions between problems. NP-completeness.
- Examples of some classical problems from the area of combinatorial optimization. Examples of problems where some of them are in P and some NP-complete.
- Some other complexity classes (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Examples of complete problems for these classes.
- Examples of techniques of design of efficient algorithms. Examples of use of these techniques for solving combinatorial problems.
- Greedy algorithms and their relationship with matroids. Branch and bound method.
- Complexity of algorithms in an average case. Amortized complexity. Examples of some more advanced data structures and of analysis of complexity of operations on these structures.
- Randomized algorithms.
- Approximation algorithms. Hardness of approximation of some problems.
- Parallel algorithms: Model of computation for parallel algorithms (PRAM). Computational complexity of parallel algorithms.
- Distributed algorithms: Models of computation for distributed algorithms, communication complexity.
- Introduction. Algorithms and algorithmic problems. Models of computation (e.g., RAM machines, Turing machines, ...). Church-Turing thesis.
- Algorithmically undecidable problems.
- Computational complexity of algorithms. Asymptotic notation. Examples of techniques used in the analysis of computational complexity of algorithms. Analysis of computational complexity of recursive algorithms.
- Complexity classes. Nondeterministic algorithms. Classes P and NP. Reductions between problems. NP-completeness.
- Examples of some classical problems from the area of combinatorial optimization. Examples of problems where some of them are in P and some NP-complete.
- Some other complexity classes (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Examples of complete problems for these classes.
- Examples of techniques of design of efficient algorithms. Examples of use of these techniques for solving combinatorial problems.
Greedy algorithms and their relationship with matroids. Branch and bound method.
- Complexity of algorithms in an average case. Amortized complexity. Examples of some more advanced data structures and of analysis of complexity of operations on these structures.
- Randomized algorithms.
- Approximation algorithms. Hardness of approximation of some problems.
- Parallel algorithms: Model of computation for parallel algorithms (PRAM). Computational complexity of parallel algorithms.
- Distributed algorithms: Models of computation for distributed algorithms, communication complexity.
Tutorials:
- Algorithms and algorithmic problems. Models of computation (e.g., RAM machines, Turing machines, ...). Church-Turing thesis.
- Algorithmically undecidable problems.
- Computational complexity of algorithms. Asymptotic notation. Examples of techniques used in the analysis of computational complexity of algorithms. Analysis of computational complexity of recursive algorithms.
- Complexity classes. Nondeterministic algorithms. Classes P and NP. Reductions between problems. NP-completeness.
- Examples of some classical problems from the area of combinatorial optimization. Examples of problems where some of them are in P and some NP-complete.
- Some other complexity classes (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Examples of complete problems for these classes.
- Examples of techniques of design of efficient algorithms. Examples of use of these techniques for solving combinatorial problems.
- Greedy algorithms and their relationship with matroids. Branch and bound method.
- Complexity of algorithms in an average case. Amortized complexity. Examples of some more advanced data structures and of analysis of complexity of operations on these structures.
- Randomized algorithms.
- Approximation algorithms. Hardness of approximation of some problems.
- Parallel algorithms: Model of computation for parallel algorithms (PRAM). Computational complexity of parallel algorithms.
- Distributed algorithms: Models of computation for distributed algorithms, communication complexity.
E-learning
Literature
[1] Sawa, Z.: Theory of algorithms (slides for the course), VŠB-TU, Ostrava, 2025 (available on the web-page of the course).
[2] Michael Sipser: Introduction to the Theory of Computation, Thomson 2006.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[2] Michael Sipser: Introduction to the Theory of Computation, Thomson 2006.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Advised literature
[4] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc, 2000.
[10] Gibbons, A., Rytter, W.: Efficient Parallel Algorithms, Cambridge University Press, 1989.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc, 2000.
[10] Gibbons, A., Rytter, W.: Efficient Parallel Algorithms, Cambridge University Press, 1989.