Vassar CMPU 240: Theory of Computation

Tuesday	1:30–2:45 p.m.
Thursday	1:30–2:45 p.m.

Sanders Physics 105

Professor Gordon

↓ Current

Part 1: Regular languages	Tuesday	Thursday
Models of computation Read Syllabus Read How to Succeed Read § 0		Jan. 22 Theory of computation
Finite automata Read § 1.1 Assignment 1	Jan. 27 Languages and automata	Jan. 29 Deterministic finite automata
Nondeterminism Read § 1.2 Read Guide to Proofs Assignment 2	Feb. 3 Nondeterministic finite automata	Feb. 5 Relating DFAs and NFAs
Models of the regular languages Read § 1.3 Assignment 3	Feb. 10 Properties of regular languages	Feb. 12 Regular expressions
End of Part 1 Read § 1.4	Feb. 17 The limits of regular languages	Feb. 19 Review
Part 2: Context-free languages
Context-free grammars Read § 2.1 Assignment 4	Feb. 24 Exam 1	Feb. 26 Context-free grammars
Models of the context-free languages Read § 2.2 Assignment 5	Mar. 3 Context-free grammars and context-free languages	Mar. 5 Pushdown automata
Spring break	Mar. 10 🐥	Mar. 12 🐝
Spring break	Mar. 17 🌧	Mar. 19 🌱
Context-free and non-context-free languages Read § 2.2 Assignment 6	Mar. 24 The power of PDAs	Mar. 26 The limits of context-free languages
End of Part 2	Mar. 31 Parsing with CFGs	Apr. 2 Review
Part 3: Beyond context-free
Turing machines Read § 3.1–3.2 Assignment 7	Apr. 7 Exam 2	Apr. 9 Turing machines
Decidable languages Read § 3.3 Assignment 8	Apr. 14 Designing Turing machines	Apr. 16 Turing machines and computation
The limits of computation Read § 4.1–4.2 Assignment 9	Apr. 21 At the foot of the mountains of undecidability	Apr. 23 The limits of computation
Computability Read § 5.1–5.3 Read reductions handout Assignment 10 ECS	Apr. 28 Reductions and computability	Apr. 30 The big picture
End of Part 3	May 5 Review	May 7 📚
	May 12 📚	Exam 3 to be scheduled during finals week

Part 1: Regular languages

Tuesday

Thursday

Models of computation

Read Syllabus
Read How to Succeed
Read § 0

Jan. 22

Theory of computation

Finite automata

Read § 1.1
Assignment 1

Jan. 27

Languages and automata

Jan. 29

Deterministic finite automata

Nondeterminism

Read § 1.2
Read Guide to Proofs
Assignment 2

Feb. 3

Nondeterministic finite automata

Feb. 5

Relating DFAs and NFAs

Models of the regular languages

Read § 1.3
Assignment 3

Feb. 10

Properties of regular languages

Feb. 12

Regular expressions

End of Part 1

Read § 1.4

Feb. 17

The limits of regular languages

Feb. 19

Review

Part 2: Context-free languages

Context-free grammars

Read § 2.1
Assignment 4

Feb. 24

Exam 1

Feb. 26

Context-free grammars

Models of the context-free languages

Read § 2.2
Assignment 5

Mar. 3

Context-free grammars and context-free languages

Mar. 5

Pushdown automata

Spring break

Mar. 10

🐥

Mar. 12

🐝

Spring break

Mar. 17

🌧

Mar. 19

🌱

Context-free and non-context-free languages

Read § 2.2
Assignment 6

Mar. 24

The power of PDAs

Mar. 26

The limits of context-free languages

End of Part 2

Mar. 31

Parsing with CFGs

Apr. 2

Review

Part 3: Beyond context-free

Turing machines

Read § 3.1–3.2
Assignment 7

Apr. 7

Exam 2

Apr. 9

Turing machines

Decidable languages

Read § 3.3
Assignment 8

Apr. 14

Designing Turing machines

Apr. 16

Turing machines and computation

The limits of computation

Read § 4.1–4.2
Assignment 9

Apr. 21

At the foot of the mountains of undecidability

Apr. 23

The limits of computation

Computability

Read § 5.1–5.3
Read reductions handout
Assignment 10
ECS

Apr. 28

Reductions and computability

Apr. 30

The big picture

End of Part 3

May 5

Review

May 7

📚

May 12

📚

Exam 3 to be scheduled during finals week

Present-day computers are built of transistors and wires, but they could just as well be built, according to the same principles, from valves and water pipes, or from sticks and string. The principles are the essence of what makes a computer compute. One of the most remarkable things about computers is that their essential nature transcends technology.

W. Daniel Hillis, The Pattern on the Stone, 1998