Sept. 25th, 2023: 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. 27th, 2023: Non-deterministic automata and their equivalence to DFA; closure properties of regular languages.

Book: [S] chapt. 1.2

Oct. 2nd, 2023: Regular expressions and their equivalence with finite automata.

Book: [S] chapt. 1.3

Oct. 4th, 2023: Regular grammars and their equivalence with finite automata; coincidence of right-linear and left-linear grammars.

Book: [HU] chapt. 9.1

Oct. 9th, 2023: The pumping lemma for regular languages; proofs of non-regularity for some languages.

Book: [S] chapt. 1.3

Oct. 11th, 2023: Exercises on the first 5 classes

Oct. 16th, 2023: 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. 18th, 2023: Pumping lemma for context-free languages; proofs of non-context-freedom for some languages.

Book: [S] chapt 2.3

Oct. 23rd, 2023: 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. 25th, 2023: Turing machines: formal definition and its variants (non-deterministic and multi-tape).

Book: [S] chapt's 3.1 and 3.2

Oct. 30th, 2023: 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

Nov. 6th, 2023: Exercises on the second 5 classes

Nov. 8th, 2023: Church-Turing thesis; definition of algorithm; problems as languages; decision vs optimization problems.

Book: [S] chapt 3.3

Nov. 13th, 2023: 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. 15th, 2023: 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. 20th, 2023: 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. 22nd, 2023: 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. 27th, 2023: 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).

Nov. 29th, 2023: 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. 4th, 2023: 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. 11th, 2023: PTAS for the subset sum problem.

Book: [CLR] chapt 35.5.

Dec. 13th, 2023: 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).

Dec. 18th, 2023: Exercises on the last classes.

Dec. 20th, 2023: Simulation of the exam (both written and oral).