Computer Science COMP3630/COMP6363

Theory of Computation

Lectures

Lecture notes will not be available on the web. Almost all of the course content can be found in the textbook.

Tutorials

There will not be separate tutorials for this course. Some of the lectures might be run in tutorial mode.

Assignment Scheme

The course will have 4 assignments, totalling 30%, and one written exam which values at 70%.

Textbook

J. E. Hopcropft, R. Motwani, J. D. Ullman,
Automata Theory, Languages, and Computation.
3rd edition, Pearson Eduction, 2007.

Further Reading

M. R. Garey and D. S. Johnson,
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman & Co., New York, 1979.

Lecturers

Andreas Bauer
Room B245, RSISE Building
6125 8611; baueran(at)rsise.anu.edu.au

Brendan McKay (course coordinator)
Room N336, CSIT Building
6125 3845; bdm(at)cs.anu.edu.au

Jinbo Huang
National ICT (NICTA)
Level 1, Tower A
7 London Circuit
6267 6216; Jinbo.Huang(at)nicta.com.au

Handouts

Assignment 1

α-β lemma

Assignment 2

Assignment 3

Assignment 4