Theory of Algorithms

Content:

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.

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.

References:

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-60E (sufficient)
61-70D (satisfactory)
71-80C (good)
81-90B (very good)
91-100A (excellent)