Past editions: Spring ‘20, Fall ‘19

CS 420: Introduction to the Theory of Computation

Fall 2021

Course information

  • Location: (M01-0409) Room 409, 1st floor, McCormack
  • Schedule: 4:00pm to 5:15pm on Monday, Wednesday

Instructor contact

  • Email: Tiago.Cogumbreiro@umb.edu
  • Office: (M03-0201-16) Room 0201-16, 3rd floor, McCormack
  • Office hours: 3:00pm to 4:00pm Wednesday, Thursday, Friday

Teaching assistants contact

  • Dennis Liew
  • Office hours: 12:30pm to 1:30pm on Tuesday, Wednesday, and Thursday.

  • Hannah Zicarelli
  • Office hours: 5:30pm to 6:30pm on Monday, Tuesday, and Wednesday.

Resources

Class Schedule

Note: Any lecture titles in future dates are considered tentative.

Date # Lecture
☙ Module 1: Logical Foundations ❧
Mo, Sep 6 (School closure)
We, Sep 8 01 Course overview; Coq intro
Mo, Sep 13 02 Pattern matching; reflexivity
We, Sep 15 03 Proofs by induction
Mo, Sep 20 04 Manipulating theorems; data-structures
We, Sep 22 05 Polymorphism; Constructor injectivity, explosion principle
Mo, Sep 27 06 Logical Connectives
We, Sep 29 07 Mini-test 1 recap
☙ Module 2: Regular Languages ❧
Mo, Oct 4 08 Formal languages
We, Oct 6 09 Kleene star, language equivalence
Mo, Oct 11 (School closure)
We, Oct 13 10 Recap & exercises (no slides)
Mo, Oct 18 11 Regular expressions
We, Oct 20 12 REGEX & Nondeterministic Finite Automata
Mo, Oct 25 13 NFA ⇔ REGEX
We, Oct 27 14 Deterministic Finite Automata; NFA ⇔ DFA
☙ Module 3: Context-free Languages ❧
Mo, Nov 1 15 Pumping lemma; Non-regular languages
Playlist on proving irregularity with Coq
We, Nov 3 16 Context-free grammars
Mo, Nov 8 17 Pushdown Automata
We, Nov 10 18 PDA ⇔ CFG
Mo, Nov 15 19 Pumping lemma; Non-context-free Languages; Turing Machines
We, Nov 17 20 Variants of Turing Machines
We, Nov 17 21 Acceptance, emptiness and equality tests
☙ Module 4: Decidability ❧
Mo, Nov 22 22 Undecidability
We, Nov 24 23 QA session (no slides)
Mo, Nov 29 24 Undecidable problems
We, Dec 1 25 Undecidable problems
Mo, Dec 6 26 Mapping reducibility
We, Dec 8 27 QA Session
Homework 8 tutorial
Homework 7 tutorial
Mo, Dec 13 28 QA Session