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 "CS422:".


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/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 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)



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: