Theory of Computation 2022 — различия между версиями
м |
м |
||
| Строка 7: | Строка 7: | ||
= Dates and Deadlines = | = Dates and Deadlines = | ||
| − | Homeworks 1, 2, 3: September 26 | + | Homeworks 1, 2, 3: September 26 |
| − | Homeworks 4, 5, 6: October 17 | + | |
| − | Homeworks 7, 8, 9: November 14 | + | Homeworks 4, 5, 6: October 17 |
| − | Homeworks 10, 11, 12: December 5 | + | |
| + | Homeworks 7, 8, 9: November 14 | ||
| + | |||
| + | Homeworks 10, 11, 12: December 5 | ||
= Grading = | = Grading = | ||
Версия 18:44, 9 сентября 2022
Содержание
Classes
Lectures: Monday 13:00 - 14:20 by Bruno Bauwens and Alexey Talambutsa
Seminars: Monday 14:40 - 16:00 by Pavel Zakharov
Dates and Deadlines
Homeworks 1, 2, 3: September 26
Homeworks 4, 5, 6: October 17
Homeworks 7, 8, 9: November 14
Homeworks 10, 11, 12: December 5
Grading
Colloquium: 35%
Homework: 35%
Exam: 30%
Homework Grading
Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems.
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)
| Summary | Problem list | |
|---|---|---|
| 05.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem set 1 |
| 12.09 | Time and space hierarchy theorems. Time and space constructible functions. | |
| 19.09 | Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness. | |
| 26.09 | Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. | |
| 3.10 | Inclusions between P, NP, and PSPACE. Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | |
| 10.10 | P is a subset of P/poly, Cook–Levin theorem, NP-completeness of: subsetsum, set-splitting, 3-colorability and exactly 1-in-3 SAT. | |
| 17.10 | Space complexity. Classes L, NL, PSPACE and NPSPACE. Directed Reachability is in SPACE(log^2 n). Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s. | |
| 31.10 | PSPACE completeness of generalized geography. Oracle computation definitions. There exists an oracle A for which PA = NPA. There is an oracle B such that PB is not equal to NPB. | |
| 07.11 | Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Most of it is also here | |
| 14.11 | Streaming algorithms: finding the majority element, computation of the number of different elements in logarithmic space. See Chapts 6.1-6.2 in foundations of datascience by Avrim Blum and others. Another nice chapter in Tim Roughgarden's lecture notes | |
| 21.11 | Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. | |
| 28.11 | Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. Slides. | |
| 05.12 | Colloquium. | |
| 12.12 | Complexity of clustering: an exact algorithm for maximizing the inter-cluster distance and an approximate algorithm for minimizing the intra-class distance. | Sample exam |
For interested students, there are 3 lectures in parameterized complexity.
12 Sept: Fixed parameter tracktability and examples, presentation.
19 Sept: Topics from chapters 1 and 2 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.
26 Sept: The W-hierarchy, chapter 13 in the same book.
Office hours
Bruno Bauwens: Tuesdays 14h-20h. It is best to warn a day ahead on brbauwens -a- gmail.com
Alexey Talambutsa: First contact by email.
