Foundations of Computation (CS580 A7): Fall 2023



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/21-8/27 Introduction, DFAs, NFAs, closure properties,
Abstract Syntax Trees (AST)
MCS: Chapter 1,
MCS: Sections 4.1,4.2,4.3;
Chapter 0, Chapter 1 (till page 54)
Homework 0, Homework 1
8/28-9/01 NFAs, determinization: subset construction,
closure properties, regular expressions
Chapter 1 till page 66 Homework 2,
Prereq Quiz (Sets, Propositional logic)
9/05-9/09 CS220 revisit (Sets, Propositional logic),
Regular expressions, non-regular languages
Chapter 1, till Section 1.3 Homework 3
9/12-9/16 Pumping lemma and non-regular languages,
Characterizing non-regular languages, first order logic
Chapter 1,
Gersting: Sections 1.1, 1.2
Homework 4
9/19-9/23 First order logic Henkin-Hintikka evaluation games,
DFA minimization
Gersting: Sections 1.2, 1.3 Homework 5
9/26-9/30 Myhill-Nerode Theorem, Context-free grammars, review Section 2.1 Midterm prep
10/03-10/05 Midterm 1, Pushdown automata Section 2.2 Homework 6
10/10-10/14 Midterm 1 solutions, PDA-CFG equivalence Section 2.3 Homework 7
10/17-10/21 Pumping lemma for CFLs, CYK algorithm,
Turing machines
Chapter 3 Homework 8
10/24-10/28 Non-deterministic Turing machines, Undecidability Chapter 4 Homework 9
10/31-11/04 Undecidability, Turing reducibility Sections 5.1, 6.3 Midterm prep
11/07-11/11 Review, Midterm 2 (comprehensive) Midterm prep
11/14-11/18 Many-one reducibility Section 5.3 Homework 10
11/28-12/02 Midterm solutions, theories in first order logic,
arithmetic heirarchy
Homework 11
12/05-12/09 Review
12/12-12/16 Final exam (open book)




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: