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:

Brief content of lectures Lectures.

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 5th 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 8th 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 35 points, with 60 minutes allowed for solving them.

The oral part will look at theory and can bring maximum 30 points; can be taken by those who gained at least 35 points from all the written tests and at least 10 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 35 points or T is smaller than 10 points, the student failed the exam.

2) If P + M + T is at least 35 points and T is at least 10 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-59E (sufficient)
60-69D (satisfactory)
70-79C (good)
80-89B (very good)
90-100A (excellent)