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. Analyzing algorithms and problems, classifying functions by their growth rates.
  2. Determining time and space complexity of well known algorithms.
  3. Verifying correctness of algorithms using variants and invariants.
  4. First test.
  5. Deterministic Turing machines.
  6. Nondeterminictic Turing machines.
  7. Classes P and NP.
  8. Second test.
  9. Polynomial reductions of problems.
  10. Examples of randomized algorithms.
  11. Examples of undecidable problems.
  12. Reserve.

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.

Office hours for Summer semester 2019/20 Tuesdays 11:00 - 12:00 or by appointment.

Brief content of lectures Lectures.

Presentations Presentations.

Brief content of tutorials Tutorials.

Assesment (zapocet):

Requirements: Active participation in labs.

Exams

During semester two test are written.

First test (45 minutes) contains asymptotic growth of functions, time complexity of algorithms. It is written during the tutorial in the 6th week. Maximum gain is 15 points.

Second test (60 minutes) contains design of a Turing machine (deterministic or nedeterministic with one tape) deciding a given language, and its time complexity. It is written during the tutorial in the 9th week. Maximum gain is 20 points.

It is not possible to repeat the tests. For those who do not write the test/tests from serious reasons, possibility will be given to write the test/tests during the last week of semester.

Final Exams and Grading

Final exam contains two parts - a written part (obligatory) and an oral part (not obligatory). Written test will contain problems concerning complexity classes, maximum gain 50 points, with 90 minutes allowed for solving them.

The oral part will look at theory and can bring maximum 15 points; can be taken by those who gained at least 42 points from all the written tests and at least 20 points from the final one.

Grading:

The resulting grade is based on four inputs: Let P, M, T be the number of points gained from the first, second, and final written test, respectively. Let O be the number of points from the oral part.

1) If P + M + T is less than 42 points or T is smaller than 20 points, the student failed the exam.

2) If P + M + T is at least 42 points and T is at least 20 points, then the student can take an oral exam. The grade is then determined by the total S = P + M + T + O and the following key:

Result:

S Grade
50-59 E (sufficient)
60-69 D (satisfactory)
70-79 C (good)
80-89 B (very good)
90-100 A (excellent)