Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions

---

B4M01TAL	Theory of Algorithms
Roles:	P	Extent of teaching:	3P+2S
Department:	13101	Language of teaching:	CS
Guarantors:	Demlová M.	Completion:	Z,ZK
Lecturers:	Demlová M.	Credits:	6
Tutors:	Demlová M., Žukovec N.	Semester:	L

Web page:

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

Anotation:

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 outline:

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:

[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

Requirements:

Subject is included into these academic programs:

Program	Branch	Role	Recommended semester
MPOI1_2018	Human-Computer Interaction	P	2
MPOI9_2018	Data Science	P	2
MPOI8_2018	Bioinformatics	P	2
MPOI7_2018	Artificial Intelligence	P	2
MPOI6_2018	Software Engineering	P	2
MPOI5_2018	Computer Vision and Image Processing	P	2
MPOI4_2018	Computer Engineering	P	2
MPOI3_2018	Computer Graphics	P	2
MPOI2_2018	Cyber Security	P	2

---

Page updated 12.10.2024 17:51:12, semester: L/2023-4, Z,L/2024-5, Z/2025-6, Send comments about the content to the Administrators of the Academic Programs

Proposal and Realization: I. Halaška (K336), J. Novák (K336)