Theory of Computation 2022

Classes

Lectures: Monday 13:00 - 14:20 by Bruno Bauwens and Alexey Talambutsa

Seminars: Monday 14:40 - 16:00 by Pavel Zakharov

Grading

Colloquium: 35%
Homework: 35%
Exam: 30%

Homework Grading

Some homework assignments contain extra problems. Let us call all other problems regular. The weight of each problem (whether regular or extra) in the overall homework grade is 8/n, where n is the total number of regular problems in all homework assignments. Partial credit is possible for some problems.

If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.

Exam

The exam consists of 8 questions of the same level as the homework.

You may use all notes, books, and other reference materials. However, the solutions you submit must, of course, be your own. You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.

You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.

Course Materials

The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 7–10.

If you need some background in math, consider these two sources:
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)

Video	Summary	Problem list
05.09	Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples (one, two). Time and space complexity. Complexity classes P, PSPACE, EXP.	Problem set 1