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 Monday, Wednesday (remotely or in-person)

Teaching assistants contact

  • Kleopatra Gjini (REMOTE): Mondays and Wednesdays 11am-12pm; Fridays 10am-11am

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
We, Oct 19 12 REGEX & Nondeterministic Finite Automata
Mo, Oct 24 13 NFA ⇔ REGEX
We, Oct 26 14 Deterministic Finite Automata; NFA ⇔ DFA
֍ Context-free Languages ֍
Mo, Oct 31 15 Pumping lemma; Non-regular languages
We, Nov 2 16 Context-free grammars
Mo, Nov 7 17 Pushdown Automata
We, Nov 9 18 PDA ⇔ CFG
Mo, Nov 14 19 Pumping lemma; Non-context-free Languages; Turing Machines
We, Nov 16 20 Variants of Turing Machines
Mo, Nov 21 21 Acceptance, emptiness and equality tests
֍ Decidability ֍
We, Nov 23 22 Undecidability
Mo, Nov 28 23 QA session
We, Nov 30 24 Undecidable problems
Mo, Dec 5 25 Undecidable problems
We, Dec 7 26 Mapping reducibility
Mo, Dec 12 27 QA Session
We, Dec 14 28 QA Session