Theory of Algorithms

Garant předmětu:

Marie Demlová

Lecturer:

Marie Demlová

Tutor:

Marie Demlová, Natalie Žukovec

Supervisor:

Department of Mathematics

Synopsis:

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.

Requirements:

Syllabus of lectures:

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.

Syllabus of tutorials:

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.

Study Objective:

Study materials:

[1] Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991

[2] Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 2002

[3] Talbot, J., Welsh, D.: Complexity and Cryptography, Cambridge University Press, 2006

Note:

Further information:

http://math.feld.cvut.cz/demlova/teaching/tal_vyuka.html pro ceskou verzi, https://math.feld.cvut.cz/demlova/teaching/e-tal_vyuka.html for english version

Time-table for winter semester 2023/2024:

Time-table is not available yet

Time-table for summer semester 2023/2024:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomT2:D3-209 Demlová M. 08:15–10:45 (lecture parallel1) Dejvice T2:D3-209
Wed	roomT2:C3-52 Žukovec N. 09:15–10:45 (lecture parallel1 parallel nr.104) Dejvice T2:C3-52roomT2:C3-52 Demlová M. 14:30–16:00 (lecture parallel1 parallel nr.101) Dejvice T2:C3-52roomT2:C3-52 16:15–17:45 (lecture parallel1 parallel nr.106) Dejvice T2:C3-52 roomT2:C3-51 Demlová M. 11:00–12:30 (lecture parallel1 parallel nr.102) Dejvice T2:C3-51roomT2:C3-52 Žukovec N. 12:45–14:15 (lecture parallel1 parallel nr.105) Dejvice T2:C3-52 roomT2:C3-52 Žukovec N. 11:00–12:30 (lecture parallel1 parallel nr.108) Dejvice T2:C3-52
Thu
Fri

The course is a part of the following study plans:

• Open Informatics - Human-Computer Interaction (compulsory course in the program)
• Open Informatics - Cyber Security (compulsory course in the program)
• Open Informatics - Computer Graphics (compulsory course in the program)
• Open Informatics - Computer Engineering (compulsory course in the program)
• Open Informatics - Computer Vision and Image Processing (compulsory course in the program)
• Open Informatics - Software Engineering (compulsory course in the program)
• Open Informatics - Artificial Intelligence (compulsory course in the program)
• Open Informatics - Bioinformatics (compulsory course in the program)
• Open Informatics - Data Science (compulsory course in the program)