# Theory of Algorithms

This is a grouped course. It consists of several seperate subjects that share learning materials, assignments, tests etc. Below you can see information about the individual subjects that make up this subject.
##### Theory of Algorithms A4M01TAL
 Credits 6 Semesters Summer Completion Assessment + Examination Language of teaching Czech Extent of teaching 3P+1S
Annotation
The course brings theoretical background of the theory of algorithms with the focus at first on the time and space complexity of algorithms and problems, secondly on the correctness of algorithms. Further it is dealt with the theory of complexity; the classes P, NP, NP-complete, PSPACE and NPSPACE are treated and properties of them investigated. Probabilistic algorithms are studied and the classes RP and ZZP introduced.
Course outlines
1. Analyzing algorithms and problems, classifying functions by their growth rates, time and space complexity.
2. Correctness of algorithms, variants and invariants.
3. Decision problems and optimization problems.
4. Turing machine and its variants.
5. Relation between Turing machine and RAM machine.
6. Classes P and NP.
7. Reduction and polynomial reduction of problems.
8. NP-complete problems, Cook's Theorem.
9. Classes PSPACE and NPSPACE..
10. Randomized algorithms with polynomial time complexity.
11. Classes RP and ZZP.
12. Undecidable problems.
13. Reserve.
Exercises outlines
1. Determining time and space complexity of well known algorithms.
2. Verifying correctness of algorithms using variants and invariants.
3. Turing machines.
4. Polynomial reductions of problems.
5. Examples of randomized algorithms.
6. Examples of undecidable problems.

Literature
 Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991
 Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 2002
 Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001
Requirements
Logic and Graphs, Discrete Mathematics
##### Theory of Algorithms (Main course) B4M01TAL
 Credits 6 Semesters Summer Completion Assessment + Examination Language of teaching Czech Extent of teaching 3P+2S
Annotation
The course brings theoretical background of the theory of algorithms with the focus at first on the time and space complexity of algorithms and problems, secondly on the correctness of algorithms. Further it is dealt with the theory of complexity; the classes P, NP, NP-complete, PSPACE and NPSPACE are treated and properties of them investigated. Probabilistic algorithms are studied and the classes RP and ZZP introduced.
Course outlines
1. Analyzing algorithms and problems, classifying functions by their growth rates, time and space complexity.
2. Correctness of algorithms, variants and invariants.
3. Decision problems and optimization problems.
4. Turing machine and its variants.
5. Relation between Turing machine and RAM machine.
6. Classes P and NP.
7. Reduction and polynomial reduction of problems.
8. NP-complete problems, Cook's Theorem.
9. Classes PSPACE and NPSPACE..
10. Randomized algorithms with polynomial time complexity.
11. Classes RP and ZZP.
12. Undecidable problems.
13. Reserve.
Exercises outlines
1. Determining time and space complexity of well known algorithms.
2. Verifying correctness of algorithms using variants and invariants.
3. Turing machines.
4. Polynomial reductions of problems.
5. Examples of randomized algorithms.
6. Examples of undecidable problems.
Literature
 Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991
 Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 2002
 Talbot, J., Welsh, D.: Complexity and Cryptography, Cambridge University Press, 2006