Theoretical Computer Science 2022
Материал из Wiki - Факультет компьютерных наук
Версия от 15:34, 19 января 2022; Bbauwens (обсуждение | вклад)
Classes
Wednesdays 18:10–21:00, room TBA, zoomlink
Dates and Deadlines
Grading
Exam: 40%
Homework: 20%
Project: 40%
Course Materials
The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", chapters 1, 2–7.
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 |
|---|---|---|
| 19.01 | 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
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 || Problem set 10 |
| 23.11 | Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. Slides | Problem set 11 |
| 30.11 | Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. Slides. Seminar. | Problem set 12 |
| 07.12 | Colloquium. | |
| 14.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
--> |
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Bruno Bauwens, S834, Zoom | 14:00-20:00 |
