Theory of Algorithms

Lecturer:

Marie Demlová (gar.)

Tutor:

Marie Demlová (gar.), Jiřina Scholtzová

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:

Logic and Graphs, Discrete Mathematics

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] Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

	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:C3-340 Demlová M. 08:15–10:00 (lecture parallel1) Dejvice Posluchárna
Fri	roomT2:A4-205 Scholtzová J. 07:30–09:00 ODD WEEK (lecture parallel1 parallel nr.101) Dejvice UčebnaroomT2:A4-205 Scholtzová J. 09:15–10:45 ODD WEEK (lecture parallel1 parallel nr.103) Dejvice UčebnaroomT2:A4-205 Demlová M. 11:00–12:30 ODD WEEK (lecture parallel1 parallel nr.105) Dejvice Učebna roomT2:A4-205 07:30–09:00 EVEN WEEK (lecture parallel1 parallel nr.102) Dejvice UčebnaroomT2:A4-205 Scholtzová J. 09:15–10:45 EVEN WEEK (lecture parallel1 parallel nr.104) Dejvice UčebnaroomT2:A4-205 11:00–12:30 EVEN WEEK (lecture parallel1 parallel nr.106) Dejvice Učebna
Thu
Fri	roomT2:C3-340 Demlová M. 12:45–14:15 EVEN WEEK (lecture parallel1) Dejvice Posluchárna

The course is a part of the following study plans:

• Otevřená informatika - Umělá inteligence (compulsory course in the program)
• Otevřená informatika - Počítačové inženýrství (compulsory course in the program)
• Otevřená informatika - Počítačové vidění a digitální obraz (compulsory course in the program)
• Otevřená informatika - Počítačová grafika a interakce (compulsory course in the program)
• Otevřená informatika - Softwarové inženýrství (compulsory course in the program)
• Biomedicínské inženýrství a informatika - Biomedicínská informatika (compulsory course of the specialization)
• Computer Technology - New - Software Engineering- structured studies (compulsory course of the branch)
• Computer Technology - New - Computer Network and Internet- structured studies (compulsory course of the branch)