I assume students to be very familiar with the language of mathematics (sets, functions, proofs, ...). Hence, chapter 0 of [S] will be assumed. I strongly suggest all students to read that chapter to be sure that all those definitions are already in their background (and study them if they are not).
Sept. 22nd, 2025: Introduction to the course. Alphabets, strings and languages; regular languages and (deterministic) finite state automata.
Book: [S] chapt.'s 0.1, 0.2 and 1.1
Sept. 24th, 2025: Non-deterministic automata and their equivalence to DFA.
Book: [S] chapt. 1.2
Sept. 29th, 2025: Closure properties of regular languages. Regular expressions and their equivalence with finite automata.
Book: [S] chapt. 1.3
Oct. 1st, 2025: Regular grammars and their equivalence with finite automata; coincidence of right-linear and left-linear grammars.
Book: [HU] chapt. 9.1
Oct. 6th, 2024: The pumping lemma for regular languages; proofs of non-regularity for some languages.
Book: [S] chapt. 1.3
Oct. 8th, 2025: Exercises on the first 5 classes
Oct. 13th, 2025: Context-free languages: CF grammars, PDA, and their equivalence. Determinism in the setting of CF languages, and comparison with the power of non-determinism.
Book: [S] chapt's 2.1 and 2.2
Oct. 15th, 2025: Pumping lemma for context-free languages; proofs of non-context-freedom for some languages.
Book: [S] chapt 2.3
Oct. 20th, 2025: Context-sensitive languages and a few examples of context-sensitive grammars; type 0 grammars; Chomsky hierarchy.
Book: [HU] chapt's 9.2 (without equivalence with TMs) and 9.3 (without equivalence with LBA)
Oct. 22nd, 2025: Turing machines: formal definition and its variants (non-deterministic and multi-tape).
Book: [S] chapt's 3.1 and 3.2
Oct. 27th, 2025: Equivalence between Turing machines and Type 0 grammars. Definition of linear bounded automata (LBA); proof of their equivalence with CS grammars.
Book: [HU] chapt's 9.2 and 9.3
Oct. 29th, 2025: Exercises on the second 5 classes
Nov. 10th, 2025: Church-Turing thesis; definition of algorithm; problems as languages; decision vs optimization problems.
Book: [S] chapt 3.3
Nov. 12th, 2025: Decidability and Decidable problems for formal languages.
Book: [S] chapt 4.1 (and the decidability of membership problem for LBA in chapt. 5.1 -- lemma 5.8 and thm. 5.9)
Nov. 17th, 2025: Undecidability and undecidable problems for formal languages.
Book: [S] chapt 4.2 and 5.1; Rice's theorem is in exercise 5.28 and its solution
Nov. 19th, 2025: Time complexity, complexity relations among models and time complexity classes; Classes P and NP; representing the input and polynomially-related encodings.
Book: [S] chapt 7.1, 7.2, and 7.3; [CLR] chapt 34.1 and 34.2
Nov. 24th, 2025: NP-completeness: definition; polynomial reducibility and techniques for proving NP-completeness; Cook-Levin theorem.
Book: [S] chapt 7.4; [CLR] chapt 34.3 (NO circuit satisfiability).
Nov. 26th, 2025: NP-completeness proofs by reductions: 3-CNF-SAT, SUBSET-SUM, CLIQUE, VERTEX-COVER.
Book: [CLR] chapt 34.4 and 34.5 (also [S] chapt 7.5).
Dec. 1st, 2025: Other NP-completeness proofs by reductions: HAM-PATH, U-HAM-PATH, HAM-CYCLE, TSP.
Book: [CLR] chapt 34.5 and [S] chapt 7.5 (in particular, the NP-completeness proof for HAM-PATH has been taken from [S]).
Dec. 3rd, 2025: Approximation algorithms, approximation ratio, approximation scheme, PTAS. Greedy algorithm and 2-approximation for vertex cover. 2-approximation for the traveling salesman with triangular inequality; impossibility for an approximation for the general traveling salesman problem.
Book: [CLR] chapt 35.1 and 35.2 (the greedy algorithm for vertex cover is essentially covered by 35.3; however, I suggest to read paragraph 6.1 from https://courses.engr.illinois.edu/cs473/fa2018/lec/lec/06_approx_I.pdf).
Dec. 10th, 2025: PTAS for the subset sum problem.
Book: [CLR] chapt 35.5.
Dec. 15th, 2025: Space complexity. PSPACE and PSPACE-completeness: the TQBF problem. L and NL; NL-completeness: the PATH problem; NL = coNL.
Book: [S] chapt 8 (no Formula-game, no generalized-geography, no proof of thm. 8.27).
Exercises on the last classes.
Dec. 17th, 2025: Simulation of the exam (both written and oral).