CS 271: Automata and Computation Theory

Week 1

Tue, Jan. 28

Introduction
Reading: Sipser 0, Hammack 1 & 2

Thu, Jan. 30

Deterministic finite automata
Reading: Sipser 1.1
Exercises #1 due

Week 2

Tue, Feb. 04

Nondeterministic finite automata
Reading: Sipser 1.2
Quiz #1

Thu, Feb. 06

Regular languages and their closure properties
Reading: Hammack 4
Exercises #2 due

Week 3

Tue, Feb. 11

Regular expressions
Reading: Sipser 1.3
Quiz #2

Thu, Feb. 13

Snow day!
No reading.

Week 4

Tue, Feb. 18

Nonregular languages
Reading: Sipser 1.4, Hammack 5
Quiz #3 online

Thu, Feb. 20

Context-free grammars
Reading: Sipser 2.1 slides

Week 5

Tue, Feb. 25

Context-free languages and their closure properties
Reading: Hammack 6, intersection of CF and regular languages
Quiz #4
Exercises #3 due

Thu, Feb. 27

Non–context-free languages
Reading: Sipser 2.3

Week 6

Tue, Mar. 04

Exam 1
No reading.
Problem set #2 due

Thu, Mar. 06

Turing machines; languages and input encoding
Reading: Sipser 3.1

Week 7

Tue, Mar. 11

Turing machine variants and the Church-Turing thesis
Reading: Sipser 3.2 and 3.3
Quiz #5

Thu, Mar. 13

Decidable languages
Reading: Sipser 4.1
Exercises #4 due

Week 8

Tue, Mar. 18

Spring break: No class
No reading.

Thu, Mar. 20

Spring break: No class
No reading.

Week 9

Tue, Mar. 25

Diagonalization and the halting problem
Reading: Sipser 4.2
Quiz #6

Thu, Mar. 27

Undecidable languages
No reading.
Exercises #5 due

Week 10

Tue, Apr. 01

Reductions
Reading: Sipser 5.1
Quiz #7

Thu, Apr. 03

Mapping reductions
Reading: Sipser 5.3
Problem set #3 due

Week 11

Tue, Apr. 08

Exam 2
No reading.

Thu, Apr. 10

Time complexity
Reading: Sipser 7.1

Week 12

Tue, Apr. 15

Polynomial time 1
Reading: Sipser 7.2

Thu, Apr. 17

Polynomial time 2
Reading: Sipser 7.3
Quiz #8; Exercises #6 due

Week 13

Tue, Apr. 22

Nondeterministic polynomial time
Reading: Sipser 7.4

Thu, Apr. 24

NP-completeness 1
Reading: Sipser 7.5
Quiz #9; Exercises #7 due

Week 14

Tue, Apr. 29

NP-completeness 2
No reading.
Quiz #10

Thu, May 01

NP-completeness 3
No reading.
Problem set #4 due

Fri, May 09

Final Exam