## Theory of Algorithms

### Content:

#### Lectures:

- 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.
- Reserve.

#### Tutorials:

- 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.

### References:

- D. C. Kozen: The Design and Analysis of Algorithms, Springer-Verlag,
1991.
- 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**
Lectures.

### Exams

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.

Result:

sum |
grade |

50-60 | E (sufficient) |

61-70 | D (satisfactory) |

71-80 | C (good) |

81-90 | B (very good) |

91-100 | A (excellent) |