COMP 330 Theory of Computation

Tuesday, September 3, 2013

Introduction to the course

Thursday, September 5, 2013

DFAs for determining validity of words

Tuesday, September 10, 2013

Nondeterministic finite automata

Thursday, September 12, 2013

Constructions on languages and regular expressions

Tuesday, September 17, 2013

Minimisation theory for DFAs

Thursday, September 19, 2013

Learning algorithms (optional material)

Tuesday, September 24, 2013

Right invariance, isomorphisms

Thursday, September 26, 2013

Behaviour of finite state systems

Tuesday, October 1, 2013

The pumping lemma

Thursday, October 3, 2013

More pumping lemma stuff

Tuesday, October 8, 2013

Duality

Thursday, October 10, 2013

Midterm

Tuesday, October 15, 2013

Context-free languages

Thursday, October 17, 2013

Pushdown automata

Tuesday, October 22, 2013

The pumping lemma for CFLs

Thursday, October 24, 2013

Algorithms for CFLs

Tuesday, October 29, 2013

Turing machines

Thursday, October 31, 2013

Lambda calculus (optional material)

Tuesday, November 5, 2013

The halting problem and undecidability

Thursday, November 7, 2013

Reductions and PCP

Tuesday, November 12, 2013

The structural theory of computability

Thursday, November 14, 2013

Limitations of CFLs

Tuesday, November 19, 2013

Validity in first-order logic

Thursday, November 21, 2013

Universal computable functions

Tuesday, November 26, 2013

Recursion theorem

Thursday, November 28, 2013

Gödel's incompleteness theorem (optional material)

Midterm review

Final review