Past editions: Fall ‘21, Spring ‘20, Fall ‘19
CS 420: Introduction to the Theory of Computation
Fall 2022
Course information
- Location: (Y01-1350) Room 1350, 1^{st} floor, University Hall
- Schedule: Monday, Wednesday / 4:00pm to 5:15pm
Instructor contact
- Email:
Tiago.Cogumbreiro@umb.edu
- Office: (M03-0201-16) Room 0201-16, 3^{rd} floor, McCormack
- Office hours: 4:00pm - 5:00pm Monday/Tuesday/Wednesday (in-person)
Resources
- CS420 Supplementary Material: The Turing library (Coq)
- CS420 Supplementary Material: NFA/DFA/REGEX algorithms (Python)
- Logic Foundations exercises
Class Schedule
Note: Any lecture titles in future dates are considered tentative.
Date | # | Lecture | Download |
---|---|---|---|
Mo, Sep 5 | (School closure) | ||
֍ (HW1) Logical Foundations ֍ | |||
We, Sep 7 | 01 | Course overview; Coq intro | |
Mo, Sep 12 | 02 | (HW1) Pattern matching; reflexivity | |
We, Sep 14 | 03 | (HW1) Proofs by induction | |
Classroom recording (S21) | |||
Mo, Sep 19 | 04 | (HW1/HW2) Manipulating theorems; data-structures | |
Classroom recording (S21) | |||
We, Sep 21 | 05 | (HW2) Polymorphism; Constructor injectivity, explosion principle | |
Mo, Sep 26 | 06 | (HW2) Logical Connectives | |
We, Sep 28 | 07 | (HW2) Mini-test 1 recap | |
֍ Regular Languages ֍ | |||
Mo, Oct 3 | 08 | Formal languages | |
We, Oct 5 | 09 | Kleene star, language equivalence | |
Mo, Oct 10 | (School closure) | ||
We, Oct 12 | 10 | Recap & exercises | |
Mo, Oct 17 | 11 | Regular expressions (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
We, Oct 19 | 12 | REGEX & Nondeterministic Finite Automata (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
Mo, Oct 24 | 13 | NFA ⇔ REGEX (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
We, Oct 26 | 14 | Deterministic Finite Automata; NFA ⇔ DFA (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
֍ Context-free Languages ֍ | |||
Mo, Oct 31 | 15 | Pumping lemma; Non-regular languages (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
We, Nov 2 | 16 | Context-free grammars (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
Mo, Nov 7 | 17 | Pushdown Automata (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
We, Nov 9 | 18 | PDA ⇔ CFG (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
Mo, Nov 14 | 19 | Pumping lemma; Non-context-free Languages; Turing Machines (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
We, Nov 16 | 20 | Variants of Turing Machines (no slides) | |
Slides (S21) | |||
Slides (S21) | |||
֍ Decidability ֍ | |||
Mo, Nov 21 | 21 | Acceptance, emptiness and equality tests (HW7) | |
We, Nov 23 | 22 | Undecidability | |
Mo, Nov 28 | 23 | A_{tm} is undecidable | |
We, Nov 30 | 24 | Undecidable problems (HW8) (HW7 deadline) | |
Mo, Dec 5 | 25 | Undecidable problems | |
We, Dec 7 | 26 | Mapping reducibility | |
Mo, Dec 12 | 27 | QA Session | |
We, Dec 14 | 28 | QA Session (HW8 deadline) |