Course Schedule
This page will be updated frequently with current and upcoming topics. Any content that’s colored light gray is tentative and subject to change.
In the table below, the notation \S refers to chapters, for instance (Sipser 2013, \S 2.3) refers to chapter 2 section 3 of (Sipser 2013)’s book.
Tue 08–10 (A5-104), Thu 12–14 (A5S111)
Professors: Enrique Romero
| # | Date | Topic | References |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
3 |
18/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
4 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
5 |
25/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
02/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
09/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
16/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
23/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
1hr problems: Student solutions of Homework 4; 1hr theory: pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free |
(Sipser 2013, \S 2.3) |
15 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
16 |
06/11/2025 |
No class |
|
17 |
11/11/2025 |
2hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
13/11/2025 |
1 hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1 hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
21/11/2025 |
1 hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1 hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
27/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
04/12/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
11/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
18/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, and Ullman 2007, \S 10) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |
Tue 12–14 (A5105), Fri 10–12 (A5S111)
Professors: Enrique Romero and Ilario Bonacina
| # | Date | Topic | References |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
3 |
19/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
4 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
5 |
26/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
03/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
10/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
17/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
24/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
2hr problems: Student solutions of Homework 4; |
(Sipser 2013, \S 2.3) |
15 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
16 |
07/11/2025 |
1hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
17 |
11/11/2025 |
1hr theory: Student solutions of Homework 4; pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free 1hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
14/11/2025 |
1hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
21/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
28/11/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
05/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
12/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, and Ullman 2007, \S 10) |
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
19/12/2025 |
2hr theory: Time Hierarchy Theorem, P \neq EXP, TM with oracles |
(Sipser 2013, Theorem 9.10 and corollaries (pp. 369) and \S 9.2) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |
Tue 18–20 (A5203), Thu 18–20 (A5S111)
Professors: Ilario Bonacina
| # | Date | Topic | References |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
3 |
18/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
4 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
5 |
25/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
02/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
09/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
16/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
23/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
1hr problems: Student solutions of Homework 4; 1hr theory: pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free |
(Sipser 2013, \S 2.3) |
15 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
16 |
06/11/2025 |
No class |
|
17 |
11/11/2025 |
2hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
13/11/2025 |
1 hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1 hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
21/11/2025 |
1hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
27/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
04/12/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
11/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
18/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, and Ullman 2007, \S 10) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |
Tue 16–18 (A5203), Wed 15–17 (A5S111)
Professors: Antoni Lozano
| # | Date | Topic | References |
|---|---|---|---|
1 |
09/09/2025 |
30 min: Overview of the course, administrative part; 1.30hr theory: Math background; Strings and languages; Pigeonhole principle; Cantor Diagonalization |
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17) |
2 |
10/09/2025 |
1hr theory: Finite Automata (DFAs), formalization, some closure properties (union, intersection, the product construction); 1hr lab: examples of DFAs using RACSO |
(Sipser 2013, \S 1.1) |
3 |
16/09/2025 |
2hr problems: Student solutions of Homework 1 Homework 1 is due on this class (see the racó for the exercise assigned to you) |
|
4 |
17/09/2025 |
1hr theory: NFAs, determinization of NFAs; more closure properties; 1hr lab: construction of DFAs using RACSO; minimization of DFAs (Moore’s algorithm) In (Sipser 2013) the minimization of DFAs is only done in Problem 1.51, 1.52, and 7.42. |
(Sipser 2013, \S 1.2) |
5 |
23/09/2025 |
2hr problems: Student solutions of Homework 2 Homework 2 is due on this class (see the racó for the exercise assigned to you) |
|
6 |
30/09/2025 |
2hr problems: Student solutions of Homework 2 |
|
7 |
01/10/2025 |
2hr lab: construction of DFAs using RACSO |
|
8 |
07/10/2025 |
2hr theory: regular expressions and equivalence with NFAs/DFAs; Pumping Lemma; \{a^nb^n\mid n\in \mathbb N\} is not regular; proving non-regularity using closure properties |
(Sipser 2013, \S 1.3 and \S 1.4) |
9 |
08/10/2025 |
2hr lab: exercises on regular operations on RACSO |
|
10 |
14/10/2025 |
2hr problems: Student solutions of Homework 3 Homework 3 is due on this class (see the racó for the exercise assigned to you) |
|
11 |
15/10/2025 |
1ht theory: Context-free grammars (CFG); Ambiguity; 1hr lab: construction of CFGs using RACSO |
(Sipser 2013, \S 2.1) |
12 |
21/10/2025 |
2hr problems: Student solutions of Homework 4 Homework 4 is due on this class (see the racó for the exercise assigned to you) |
|
13 |
22/10/2025 |
2hr lab: construction of CFGs using RACSO; |
|
14 |
28/10/2025 |
1hr problems: Student solutions of Homework 4; 1hr theory: pumping lemma for CFL; \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free |
(Sipser 2013, \S 2.3) |
15 |
29/10/2025 |
1hr theory: Pushdown-Automata, formalization, equivalence betwen PDAs and CFGs; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2 and \S 2.4) |
16 |
03/11/2025 10:30 – 12:30 |
Midterm 1 |
|
17 |
11/11/2025 |
2hr theory: Turing Machines, basic properties, Church-Turing Thesis, Gödel numbering, Universal TM |
(Sipser 2013, \S 3) |
18 |
12/11/2025 |
1hr theory: closure of CFL under intersection with regular languages and inverse homomorphism; 1hr lab: construction of PDAs using RACSO; |
(Sipser 2013, \S 2.2) |
19 |
18/11/2025 |
1hr problems: Student solutions of Homework 5 1hr theory: RE \cap coRE = R, projection theorem Homework 5 is due on this class (see the racó for the exercise assigned to you) |
(Sipser 2013, \S 4) |
20 |
19/11/2025 |
1.30hr theory: K \in RE\setminus R, reductions 30min lab: construction of reductions from K using RACSO; |
(Sipser 2013, \S 5) |
21 |
25/11/2025 |
2hr problems: Student solutions of Homework 5 |
|
22 |
26/11/2025 |
1hr theory: Rice Theorem 1hr lab: construction of reductions from K using RACSO; (Sipser 2013) proves Rice’s Theorem only in Problem 5.28. |
|
23 |
02/12/2025 |
2hr problems: Student solutions of Homework 6 Homework 6 is due on this class (see the racó for the exercise assigned to you) |
|
24 |
03/12/2025 |
2hr lab: construction of reductions to CFGs using RACSO |
|
25 |
09/12/2025 |
1hr problems: Student solutions of Homework 6 1hr theory: recap of P, EXP, NP |
(Sipser 2013, \S 7.1, \S 7.2, \S 7.3, \S 7.4) |
26 |
10/12/2025 |
2hr theory: NP-completeness, polynomial-time reductions, Cook-Levin Theorem |
(Sipser 2013, \S 7.4 and \S 7.5) (Hopcroft, Motwani, and Ullman 2007, \S 10) |
27 |
16/12/2025 |
2hr problems: Student solutions of Homework 7 Homework 7 is due on this class (see the racó for the exercise assigned to you) |
|
28 |
17/12/2025 |
2hr theory: Time Hierarchy Theorem, P \neq EXP, TM with oracles |
(Sipser 2013, Theorem 9.10 and corollaries (pp. 369) and \S 9.2) |
29 |
09/01/2026 08:00 – 11:00 |
Midterm 2 |
|
30 |
19/01/2026 11:30 – 14:30 |
Final Exam |