Версия 15:36, 19 января 2022

Содержание

Wednesdays 18:10–21:00, room TBA, zoomlink

Exam: 40%
Homework: 20%
Project: 40%

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	Notes
19.01	Regular languages	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 -->

Person	Monday	Tuesday	Wednesday	Thursday	Friday
Bruno Bauwens, S834, Zoom					14:00-20:00

@@ Строка 24: / Строка 24: @@
 {| class="wikitable"
 |-
-! Video !! Summary !! Problem list
+! Video !! Summary !! Notes
 |-
-  || 19.01 || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples ([https://www.dropbox.com/s/wna14b7y7nmw3cq/tm.py?dl=0 one], [https://www.dropbox.com/s/wrl3mkeqslj3xtu/wsharpw.py?dl=0 two]). Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://www.dropbox.com/s/37eel2qayios6b3/prob_1.pdf?dl=0 Problem set 1]
+  || 19.01 || Regular languages  ||
-<!---
+<!--
 |-
 || 14.09 ||  Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/s/ow4m1z8u8r211qs/prob_2.pdf?dl=0 Problem set 2]