CS 420: Introduction to the Theory of Computation
Spring 2020
- Location: (Y01-1100) Room 1100, 1st floor, University Hall
- Schedule: 4:00pm to 5:15pm, Monday, Wednesday
- Email:
Tiago.Cogumbreiro@umb.edu
- Office: (M03-0201-16) Room 0201-16, 3rd floor, McCormack
- Office hours: 4:00pm - 5:00pm Monday/Tuesday/Wednesday (in-person)
- 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
|
|