Back

Theoretical Computer Science

Tutor (for lectures and tutorials):

News

Content of the Course

The aim of the course is to introduce students to some basics of the following areas of theoretical computer science:

Preliminary Program of Lectures

  1. Introduction. Algorithms and algorithmic problems. Models of computation (Turing machines, Random Access Machines). Church-Turing thesis.
  2. Computational complexity of algorithms. Asymptotic notation. Analysis of complexity of recursive algorithms.
  3. More advanced techniques of analysis and design of algorithms: amortized analysis, complexity of algorithm in an average case
  4. Turing machines. Computational complexity of problems. Complexity classes. Classes P and NP. Reductions between problems. NP-completeness. Some well-known NP-complete problems.
  5. Other complexity classes - PSPACE, EXPTIME, EXPSPACE, LOGSPACE, NLOGSPACE. Polynomial hierarchy.
  6. Undecidable problems. Rice' theorem.
  7. Randomized algorithms. Approximation algorithms.
  8. Computational complexity of parallel algorithms: models of computation for parallel algorithms (PRAM).
  9. Analysis of computational complexity of parallel algorithms. Class NC. Correspondence with circuits (circuit complexity).
  10. Distributed algorithms: models of computation for distributed algorithms. Communication complexity.
  11. Kolmogorov complexity.
  12. Semantics of programming languages: formal description of semantics (struktural operational semantics, denotational semantics).
  13. Methods for proving correctness of programs.
  14. Quantum computing.

Requirements for a Credit

Presentation

Topics for presentations will be published during the semester and each student will obtain an assigned topic.

To obtain a credit, it is necessary prepare the presentation in a written form and present it to a tutor. Students must show during these presentations that they understand the given topic. A particular term for the presentations will be specified during the semester.

It is possible to obtain up to 15 points for the presentation. It is necessary to obtain at least 5 points.

If some student does not obtain the necessary 5 points for his/her presentation, it is possible to do the presentation once again, however, the maximal number of points will be only 10 points in this case, while the required minimal number of points is 1 point.

Topics of presentation for winter semester 2024/25: tcs-presentations.pdf

Written Test

There will be a written test during the semester. It will be possible to get up to 20 points from this test, while the minimum necessary to obtain a credit is 10 points.

The test will be written on some of tutorials. Particular date will be specified during the semester.

There will be some alternative date specified for students that due to some important reasons (e.g., illness) can not attend the written test in the regular date.

Students that do not obtain the necessary 10 points from the written test will have the possibility to obtain these points on a correcting test. However, it will be possible to obtain only a 17 points and it will be still necessary to obtain at least 10 points. (Points for a credit will be assigned according to the correcting test in this case.)

It is necessary to obtain for the presentation and the written test in total at least 15 points.

Exam

It is possible to obtain up to 65 points for an exam. The exam will be in a written form.

In the exam, it is necessary to obtain at least 25 points.

Materials

Slides from Lectures

Slides from lectures from the school year 2024/2025 will be published here during the semester.
  • Lecture 1
    – Introduction. Algorithms and algorithmic problems. Models of computation (Turing machines and Random Access Machines). Church-Turing thesis.
    Slides: tcs-slides-01.pdf

  • Lecture 2
    – Undecidable problems. Semidecidable problems. Examples of undecidability of problems. Rice's theorem.
    Slides: tcs-slides-02.pdf

  • Lecture 3
    – Computational complexity of algorithms. Asymptotic notation. Complexity analysis of recursive algorithms.
    Slides: tcs-slides-03.pdf

  • Lecture 4
    – Complexity classes. Nondeterministic algorithms.
    Slides: tcs-slides-04.pdf

  • Lecture 5
    – NP-complete problems.
    Slides: tcs-slides-05.pdf

  • Lecture 6
    – Examples of proofs of NP-completeness of some problems.
    Slides: tcs-slides-06.pdf

  • Lecture 7
    – Complete problems for other complexity classes. Class PSPACE. PSPACE-complete problems.
    Slides: tcs-slides-07.pdf

  • Lecture 8
    – Classes L and NL. Logspace reductions. P-complete problems.
    Slides: tcs-slides-08.pdf

Exercises for tutorials

Exercises for tutorials for the school year 2024/2025 will be published here during the semester.

Animations

Supplemental Literature

Back