SI472: THEORY OF COMPUTING, FALL 2000

DR. CHRISTOPHER BROWN

SYLLABUS

List of topics by week:

1.
Introduction; Basic Objects (Chap. 1)
2.
Induction and Recursive Definitions (Chap. 2)
3.
Regular Languages: Regular Expressions (Chap. 3 - 4)
4.
Finite Automata I (Chap. 4)
5.
Finite Automata II (Chap. 4 - 5)
6.
6-Week Exam and Review
7.
Languages That Are Not Regular (Chap. 5)
8.
Context-Free Languages I (Chap. 6)
9.
Context-Free Languages II (Chap. 6)
10.
Pushdown Automata (Chap. 7)
11.
12-Week Exam and Review
12.
Context-Free Languages III (Chap. 8)
13.
Turing Machines (Chap. 9)
14.
Turing Machines and Decidability (Chap. 9) [Tuesday only, Thanksgiving]
15.
Recursive Functions I (Chap. 13)
16.
Church's Thesis (Chap. 12) [Tuesday only, Thursday is Academic Review]



Christopher W. Brown
2000-08-15