The Art of Computer Programming 3

International BSc in AI, PSL University — Fall 2026

---

Announcements

11 Oct	Class 8 happened online, so there was no quiz. There will also be no quiz in Class 9.
23 Sep	Midterm moved to 9 Nov (Class 15)
10 Sep	Course page is up. See you soon!

---

Lecture Notes

Lecture notes Gradually updated after each lecture.

---

Programme

#	Date	Topic(s)	Materials
Computability
01	Mon 14 Sep	Welcome words. Computable and uncomputable functions	exercises solutions
02	Wed 16 Sep	Decidable and undecidable languages, Rice's theorem	exercises solutions quiz
03	Mon 21 Sep	Turing machines	exercises solutions code quiz
04	Wed 23 Sep	History of programming (slides). Exercises: Markov normal algorithms (emulator)	exercises solutions quiz
05	Mon 28 Sep	Lambda calculus	exercises solutions
06	Wed 30 Sep	More lambda calculus	exercises solutions quiz
Complexity
07	Mon 5 Oct	Time complexity, classes P and Exp, time hierarchy	exercises solutions quiz
08	Wed 7 Oct	Class NP	exercises solutions
09	Mon 12 Oct	Reductions and hardness, NP-completeness of SAT and CLIQUE
10	Wed 14 Oct	More NP-complete problems: INDEPENDENT_SET, VERTEX_COVER, 3SAT, 3COLOUR, HAMILTONIAN-CYCLE, KNAPSACK	exercises hints quiz
11	Mon 19 Oct	Space complexity, classes PSpace, L and NL	exercises hints quiz
12	Wed 21 Oct	NP-complete problems in practice, SAT-solvers (slides)	exercises code
Formal Languages
13	Mon 2 Nov	Regular expressions and regular languages
14	Wed 4 Nov	Finite automata
15	Mon 9 Nov	Midterm (computability & complexity) + discussion (demo)
16	Mon 16 Nov	Nondeterministic automata, subset construction, exponential blowup
17	Wed 18 Nov	Pattern matching, Aho-Corasick
18	Mon 23 Nov	Context-free grammars
19	Wed 25 Nov	Syntax of programming languages
Review
20	Mon 30 Nov	Review of the course, open problems and perspective
Software Development (Part II)
21	Wed 2 Dec	Start of Part II: Specification, Python typing, testing, TDD
22	Mon 7 Dec	Git, code review, continuous integration, development processes
23	Wed 9 Dec
24	Mon 14 Dec	Generative AI and agentic coding tools, their failure modes
25	Wed 16 Dec
26	Wed 6 Jan	Tutorials
27	Mon 11 Jan	Open source, supply-chain security, documentation, packaging, release, archival
28	Wed 13 Jan
29	Mon 25 Jan	Final exam

---

Grading

A short quiz at the beginning of every class (except the first class in each of the two parts). A written midterm in Class 13 Class 15. A written exam at the end of the course.

Final Mark = 0.2 * Quizzes + 0.4 * Midterm + 0.4 * Exam

---

Further Reading

Michael Sipser, Introduction to the Theory of Computation
Sanjeev Arora & Boaz Barak, Computational Complexity: A Modern Approach
Dexter Kozen, Automata and Computability
George Boolos & Richard Jeffrey, Computability and Logic
J. Roger Hindley & Jonathan P. Seldin, Lambda-Calculus and Combinators: An Introduction
Scott Chacon & Ben Straub, Pro Git — git-scm.com/book/
John Ousterhout, A Philosophy of Software Design
Karl Fogel, Producing Open Source Software — producingoss.com

Acknowledgements

These course materials draw on my experience of learning theoretical computer science from Valery Alekseev, Bruno Bauwens, Evgeny Dashkov, Vladimir Podolskii, Nikolay Vereshchagin and Vladimir Zakharov, as well as on books by Dexter Kozen. Some proof ideas and exercises are adapted from their courses and books. Beyond that, their teaching has greatly influenced how I see the subject.