Schedule

Tue 1/23 - Notes 01 - Overview, Intro to DFAs

• Homework 0 (Due 1/25)

Thu 1/25 - Notes 02 - Regular Operations

• Homework 1 (Due 2/1)

Tue 1/30 - Notes 03 - NFAs

Thu 2/1 - Notes 04 - DFAs and NFAs

• Homework 2 (Due 2/8)

Tue 2/6 - Notes 05 - Closure Under Regular Operations

Thu 2/8 - Notes 06 - Regular Expressions

• Homework 3 (Due 2/15)

Tue 2/13 - Notes 07 - Regular Expressions and Regular Languages

Thu 2/15 - Notes 08 - Nonregular Languagas

• Homework 4 (Due 2/29)

Tue 2/20 - NO CLASS - Exam I

• Exam I (Due 2/26)

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

Tue 2/27 - Notes 10 - Context-Free Grammars

Thu 2/29 - Notes 11 - Pushdown Automata

• Homework 5 (Due 3/7)

Tue 3/5 - Notes 12 - Pushdown Automata and Context-Free Grammars

Thu 3/7 - Notes 13 - Pushdown Automata and Context-Free Grammars

• Homework 6 (Due 3/14)

Tue 3/12 - Notes 14 - Turing Machines

Thu 3/14 - Notes 15 - More Turing Machines

Tue 3/19 - NO CLASS - Spring Break

Thu 3/21 - NO CLASS - Spring Break

Tue 3/26 - Notes 16 - Algorithms

• Homework 7 (Due 4/2)

Thu 3/28 - Notes 17 - Decidability

Tue 4/2 - Notes 18 - The Halting Problem

• Exam II (Due 4/10)

Thu 4/4 - Notes 19 - Reducibility

• Homework 8 (Due 4/16)

Tue 4/9 - NO CLASS - Community Day

Thu 4/11 - Notes 20 - Mapping Reducibility

Tue 4/16 - Notes 20 - Mapping Reducibility

• Homework 9 (Due 4/23)

Thu 4/18 - Notes 21 - Measuring Time Complexity

Tue 4/23 - Notes 22 - P and NP

• Homework 10 (Due 4/30)

Thu 4/25 - Notes 23 - NP-Completeness

Tue 4/30 - Notes 24 - More NP-Completeness