COMP 330 Theory of Computation

Description
Mathematical models of computers, finite automata, Turing machines, counter machines, push-down machines, computational complexity.
Credits
3.0
Computer Science

Summary

Subject Semester

Midterm review

Fall 2013

Final review

Fall 2013

Lecture notes

Subject Semester

Tuesday, September 3, 2013

Introduction to the course

Fall 2013

Thursday, September 5, 2013

DFAs for determining validity of words

Fall 2013

Tuesday, September 10, 2013

Nondeterministic finite automata

Fall 2013

Thursday, September 12, 2013

Constructions on languages and regular expressions

Fall 2013

Tuesday, September 17, 2013

Minimisation theory for DFAs

Fall 2013

Thursday, September 19, 2013

Learning algorithms (optional material)

Fall 2013

Tuesday, September 24, 2013

Right invariance, isomorphisms

Fall 2013

Thursday, September 26, 2013

Behaviour of finite state systems

Fall 2013

Tuesday, October 1, 2013

The pumping lemma

Fall 2013

Thursday, October 3, 2013

More pumping lemma stuff

Fall 2013

Tuesday, October 8, 2013

Duality

Fall 2013

Thursday, October 10, 2013

Midterm

Fall 2013

Tuesday, October 15, 2013

Context-free languages

Fall 2013

Thursday, October 17, 2013

Pushdown automata

Fall 2013

Tuesday, October 22, 2013

The pumping lemma for CFLs

Fall 2013

Thursday, October 24, 2013

Algorithms for CFLs

Fall 2013

Tuesday, October 29, 2013

Turing machines

Fall 2013

Thursday, October 31, 2013

Lambda calculus (optional material)

Fall 2013

Tuesday, November 5, 2013

The halting problem and undecidability

Fall 2013

Thursday, November 7, 2013

Reductions and PCP

Fall 2013

Tuesday, November 12, 2013

The structural theory of computability

Fall 2013

Thursday, November 14, 2013

Limitations of CFLs

Fall 2013

Tuesday, November 19, 2013

Validity in first-order logic

Fall 2013

Thursday, November 21, 2013

Universal computable functions

Fall 2013

Tuesday, November 26, 2013

Recursion theorem

Fall 2013

Thursday, November 28, 2013

Gödel's incompleteness theorem (optional material)

Fall 2013