Schedule

Thu 9/4 - Notes 01 - Overview, Intro to DFAs

• Homework 0 (Due 9/5)

Tue 9/9 - Notes 02 - Regular Operations

• Homework 1 (Due 9/17)

Thu 9/11 - Notes 02 - Regular Operations

Tue 9/16 - Notes 03 - NFAs

• Homework 2 (Due 9/24)

Thu 9/18 - Notes 04 - DFAs and NFAs

Thu 9/18 - Notes 05 - Closure Under Regular Operations

Tue 9/23 - Notes 06 - Regular Expressions

• Homework 3 (Due 10/1)

Thu 9/25 - Notes 07 - Regular Expressions and Regular Languages

Tue 9/30 - Notes 08 - Nonregular Languagas

• Homework 4 (Due 10/15)

Thu 10/2 - Notes 09 - Nonregular Languages (cont'd)

• Exam I (Due 10/10)

Tue 10/7 - Notes 10 - Context-Free Grammars

Thu 10/9 - Buffer day

Mon 10/13 - NO CLASS (Fall break)

Tue 10/14 - NO CLASS (Fall break)

Thu 10/16 - Notes 11 - Pushdown Automata

• Homework 5 (Due 10/27)

Tue 10/21 - Notes 12 - Pushdown Automata and Context-Free Grammars

Thu 10/23 - Notes 13 - Pushdown Automata and Context-Free Grammars

Tue 10/28 - Notes 14 - Turing Machines

• Homework 6 (Due 11/3)

Thu 10/30 - Notes 15 - More Turing Machines

Tue 11/4 - Notes 16 - Algorithms

• Homework 7 (Due 11/17)

Thu 11/6 - Notes 17 - Decidability

• Exam II (Due 11/14)

Tue 11/11 - Notes 18 - The Halting Problem

• Homework 8 (Due 11/24)

Thu 11/13 - Notes 19 - Reducibility

Tue 11/18 - Notes 20 - Mapping Reducibility

• Homework 9 (Due 12/1)

Thu 11/20 - Notes 20 - Mapping Reducibility

Tue 11/25 - Notes 21 - Measuring Time Complexity

Wed 11/26 - NO CLASS (November break)

Thu 11/27 - NO CLASS (November break)

Fri 11/28 - NO CLASS (November break)

Tue 12/2 - Notes 22 - P and NP

• Homework 10 (Due 12/8)

Thu 12/4 - Notes 23 - NP-Completeness

Tue 12/9 - Notes 24 - More NP-Completeness