CS 420: Introduction to the Theory of Computation

Spring 2020

Course information

  • Location: (Y01-1100) Room 1100, 1st floor, University Hall
  • Schedule: 4:00pm to 5:15pm, 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

  • Son Nam Nguyen
  • Office: (M03-0152) Room 0152, 3rd floor, McCormack
  • Office hours: 1:30pm to 2:30pm, Monday, Wednesday

Resources

Class Schedule

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

Date # Lecture
☙ Module 1: Logical Foundations ❧
Mo, Jan 27 01 Course overview; Coq intro
We, Jan 29 02 Pattern matching; reflexivity
Mo, Feb 3 03 Proofs by induction
We, Feb 5 04 Manipulating theorems; data-structures
Mo, Feb 10 05 Polymorphism; Constructor injectivity, explosion principle
We, Feb 12 06 Logical Connectives
Mo, Feb 17 (School closure)
We, Feb 19 07 Mini-test 1 recap
☙ Module 2: Regular Languages ❧
Mo, Feb 24 08 Formal languages
We, Feb 26 09 Kleene star, language equivalence
Mo, Mar 2 10 Regular expressions (Mini-Test 1)
We, Mar 4 11 REGEX & Nondeterministic Finite Automata
Mo, Mar 9 12 NFA ⇔ REGEX
We, Mar 11 13 Deterministic Finite Automata; NFA ⇔ DFA
Mo, Mar 16 (School closure)
We, Mar 18 (School closure)
☙ Module 3: Context-free Languages ❧
Mo, Mar 23 14 Pumping lemma; Non-regular languages; Mini-test 2 recap
We, Mar 25 15 Context-free grammars
Mo, Mar 30 16 Pushdown Atomata
QA session
We, Apr 1 17 PDA ⇔ CFG
Mo, Apr 6 18 Pumping lemma; Non-context-free Languages; Turing Machines
We, Apr 8 19 Variants of Turing Machines
Mo, Apr 13 20 Acceptance, emptiness and equality tests
QA session
Lecture 17 of Fall'19
Lecture 18 of Fall'19
We, Apr 15 21 Undecidability
What is a PhD in CS? (Fall '19)
Mo, Apr 20 (School closure)
☙ Module 4: Decidability ❧
We, Apr 22 22 Undecidable problems
Homework 7 tutorial
Mo, Apr 27 23 Undecidable problems
We, Apr 29 24 Mapping reducibility
Homework 8 tutorial
Mo, May 4 25 Mapping reducibility
We, May 6 26 QA session
We, May 11 27 QA session
We, May 13 28 QA session