Automata, Logic, and Computation (CS480A4)


Instructor:


Course material on Canvas


Course Description:



Textbook (required):




Weekly Schedule

Week Topics Assigned reading Homework
8/26-8/30 Introduction, DFAs, NFAs, closure properties Chapter 0, Chapter 1 (till page 54) Homework 1, Homework 2
9/02-9/06 NFAs, determinization: subset construction Chapter 1 till page 60 Homework 3
9/09-9/13 NFAs, closure properties, subset construction, regular expressions Chapter 1, till Section 1.3 Homework 4
9/16-9/20 Regular expressions, Pumping lemma and non-regular languages Chapter 1
9/23-9/27 DFA minimization, Myhill-Nerode theorem Homework 5
9/30-10/04 Context-free grammars, Pushdown automata Sections 2.1, 2.2 Preparation for practice midterm
10/07-10/11 Quiz 1 (practice midterm) Midterm preparation
10/14-10/18 Midterm 1 Homework 6
10/21-10/25 Pushdown automata, pumping lemma for CFLs, CYK algorithm Sections 2.2, 2.3 Homework 7
10/28-11/01 Turing machines Chapter 3, Section 4.1 Homework 8
11/04-11/08 Decidability, Reducibility Chapter 4, Section 5.1 Homework 9
11/11-11/15 Reducibility Section 5.1 Preparation for practice midterm
11/18-11/22 Quiz 2 (Practice midterm) Midterm preparation
12/02-12/06 Midterm 2, Reducibility Chapter 5, Section 6.3
12/09-12/13 First-order logic, logical theories Section 6.2, notes Homework 10
12/16-12/17 Review, Final exam



Lectures:



Prerequisites:



Grading:

The course grade will be based on the following elements (minor adjustments to the weights may be made).

Homework and Readings: