# CS 420: Introduction to the Theory of Computation

## Fall 2019

# Final Grade Calculator

**Disclaimer: THE GRADE CALCULATOR IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND AND MIGHT PRODUCE INCORRECT RESULTS; THE CALCULATOR IGNORES YOUR HOMEWORK SUBMISSIONS.**

Test 1 (out of 100):

Project 1 (out of 13 exercises):

Test 2 (out of 80):

Test 3 (out of 100):

Attendance (out of 24)

(Edit values to update final grade)

# Course information

**Location:**Room W02-0158, 2^{nd}floor, Wheatley**Schedule:**Tuesdays & Thursdays 5:30pm to 6:45pm

# Instructor contact

**Email:**`Tiago.Cogumbreiro@umb.edu`

**Office:**Room 0201-16, 3^{rd}floor, McCormack**Office hours:**Tuesdays & Thursdays 2:30pm to 4:00pm

## Class Schedule

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

Date | # | Lecture | Section | Material | HW |
---|---|---|---|---|---|

Tu, Sep 03 | 1 | Deterministic Finite Automata | § 1.1 | HW1 | |

Th, Sep 05 | 2 | DFA operations | § 1.1 | ||

Tu, Sep 10 | 3 | Nondeterministic Finite Automata; NFA ⇔ DFA | § 1.2 | HW2 | |

Th, Sep 12 | 4 | NFA operations | § 1.2 | ||

Tu, Sep 17 | 5 | Regular expressions | § 1.3 | HW3 | |

Th, Sep 19 | 6 | Pumping lemma; Non-regular languages | § 1.4 | ||

Tu, Sep 24 | 7 | Context-free grammars | § 2.1 | HW4 | |

Th, Sep 26 | 8 | Chomsky Normal Form | § 2.1 | ||

Tu, Oct 01 | (Module 1 recap) | ||||

Th, Oct 03 | (Minit-test 1) | ||||

Tu, Oct 08 | 9 | Pushdown Atomata | § 2.2 | HW5 | |

Th, Oct 10 | 10 | PDA ⇔ CFG | § 2.2 | ||

Tu, Oct 15 | 11 | Pumping lemma; Non-context-free Languages | § 2.2 | ||

Th, Oct 17 | 12 | Turing Machines | § 3.1 | HW6 | |

Tu, Oct 22 | 13 | Variants of Turing Machines | § 3.2 | lf.zip | |

Th, Oct 24 | 14 | Functional Programming in Coq (`Basics.v` ) |
§ LF.1 | ex.v | |

Tu, Oct 29 | 15 | Proofs by induction (`Induction.v` ) |
§ LF.2 | ex.v | |

Th, Oct 31 | 16 | More tactics (`Tactics.v` ) |
§ LF.5 | ||

Tu, Nov 05 | (Module 2 recap) | ex.v | |||

Th, Nov 07 | (Mini-Test 2) | ||||

Tu, Nov 12 | 17 | Acceptance, emptiness and equality tests | § 4.1 | ||

Th, Nov 14 | 18 | Countable and uncountable sets | § 4.2 | ||

Tu, Nov 19 | 19 | TM Acceptance | § 4.2 | ||

Th, Nov 21 | 20 | Decidability | § 4.2 | HW7 | |

Tu, Nov 26 | 21 | Undecidable problems | § 4.2 | ||

Th, Nov 28 | (Thanksgiving recess) | ||||

Tu, Dec 03 | (Class cancelled) | ||||

Th, Dec 05 | 22 | Mapping reducibility | § 5.3 | ||

Tu, Dec 10 | (Module 3 recap) | ||||

Th, Dec 12 | (Mini-Test 3) |