Theory of Algorithms
- Analyzing algorithms and problems, classifying functions by their growth rates, time and space complexity.
- Correctness of algorithms, variants and invariants.
- Decision problems and optimization problems.
- Turing machine and its variants.
- Relation between Turing machine and RAM machine.
- Classes P and NP.
- Reduction and polynomial reduction of problems.
- NP-complete problems, Cook's Theorem.
- Classes PSPACE and NPSPACE.
- Randomized algorithms with polynomial time complexity.
- Classes RP and ZZP.
- Undecidable problems.
- Determining time and space complexity of well known algorithms.
- Verifying correctness of algorithms using variants and invariants.
- Turing machines.
- Polynomial reductions of problems.
- Examples of randomized algorithms.
- Examples of undecidable problems.
- D. C. Kozen: The Design and Analysis of Algorithms, Springer-Verlag,
- J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory,
Languages, and Computation, Addison-Wesley, 2001.
- D. Harel: Algorithmics: The Spirit of Computing, Addison-Wesley, 2002.
Brief content of lectures
Exam consists of a written and an oral part. The written part takes 105 minutes,
maximum gain is 70 points. Maximum gain from the oral part
is 30 points. For a succes a student has to obtain at least 35 points
from the written part.
|81-90||B (very good)|