Overview

This term is devoted to establishing a foundation for the formal study of computation. This foundation consists of tools from mathematics such as set theory, logic, and graph theory, and concepts from theoretical computer science, such as formal languages, abstract machines, problem transformations, and computational complexity. Concurrent with these topics, we will study functional programming in OCaml.

Syllabus

Week	Lecture dates	Main topics to be covered	Notes
1	October 1 October 3	Introduction, set theory [handouts] Deterministic Finite Automata [handouts]	LN1a
2	October 8 October 10	Nondetermistic Finite Automata [handouts] FA Equivalence and Minimization [handouts]	LN2a
3	October 15 October 17	Context free grammars [handouts] Pushdown Automata [handouts]	LN3a
4	October 22 October 24	Review of Lab2 Properites of CFLs [handouts]	LN4a
5	October 29 October 31	Turing Machines [handouts] Rice's theorem [handouts]
6	November 5 November 7	Recursive functions [handouts] Untyped lambda calculus [handouts]	LN5a
7	November 12 November 14	Godel's incompleteness theorem [handouts] Logic, Godel's incompleteness theorem [handouts]	LN6a
8	November 19 November 21	Complexity and NP [handouts] Graph theory [handouts]	LN7a
9	November 26	NP problems and reductions [handouts]
10	December 3 December 5	Cook's theorem [handouts] Summary [handouts]	LN8a
11	December 10 December 12