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, 1st 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, 3rd floor, McCormack
  • Office hours: 12:30pm to 2:00pm Tuesday, Thursday (in-person)

Resources

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 Atm 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)