Foundations of Computation (CS580 A7): Fall 2022


Instructor:

GTA:


Course material on Canvas
Please do not use Canvas to contact me. Use my email, and prefix the subject line with "CS580:".


Course Description:



Textbook (required):

Additional References:




Weekly Schedule (tentative)

Week Topics Assigned reading Homework
8/22-8/26 Introduction, DFAs, NFAs, closure properties MCS:Chapter 1, MCS: Sections 4.1,4.2,4.3;
Chapter 0, Chapter 1 (till page 54)
Homework 0, Homework 1
8/29-9/02 NFAs, determinization: subset construction,
closure properties, regular expressions
Chapter 1 till page 66 Homework 2,
Prereq Quiz (Sets, Propositional logic)
9/06-9/10 CS220 revisit (Sets, Propositional logic),
Regular expressions, Non-regular languages
Chapter 1, till Section 1.3 Homework 3
9/13-9/17 Pumping lemma and non-regular languages,
Characterizing non-regular languages, First order logic
Chapter 1 Homework 4
9/20-9/24 First order logic Henkin-Hintikka evaluation games,
DFA minimization
Gersting:Sections 1.2, 1.3 Homework 5
9/27-10/01 Context-free grammars, Pushdown automata, review Section 2.1 Midterm prep
10/04-10/08 Midterm 1, PDA-CFG equivalence Section 2.2 Homework 6
10/11-10/15 Midterm 1 solutions, pumping lemma for CFLs, CYK algorithm Section 2.3
10/18-10/22 Turing machines, non-determinism Chapter 3 Homework 7
10/25-10/29 Decidability, Reducibility Chapter 4, Section 5.1 Homework 8
11/01-11/05 Reducibility Sections 5.1, 5.3, 6.3
11/08-11/12 Reducibility, Review Midterm preparation
11/15-11/19 Midterm 2, Reducibility Homework 9
11/29-12/03 First-order logic Section 6.2, notes Homework 10
12/06-12/10 Midterm 2 solutions, review
12/13-12/17 Final exam



Lectures:



Prerequisites:



Grading:

The course grade will be based on the following elements (minor adjustments to the weights may be made). Some of the exams may be open book.

Homework and Readings: