Skip Navigation CECS Home | ANU Home | Search ANU

Computer Science COMP3630/COMP6363

Theory of Computation

 

Lectures

Room	Day	Time
Hancock 2.24	Monday	14:00-16:00
Hancock 2.24	Wednesday	16:00-18:00

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.

Assessment Scheme

The course will have 4 assignment of equal weight totalling 30%, and one written exam of weight 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

α-β lemma

Assignment 1 (due date April 4, not as on the file!)

Assignment 2

Assignment 3

Assignment 4

Exam papers (all of 2007 exam and half of 2010 exam)

Lecture schedule

This schedule is a guide that will be updated during the semester.

Date	Book sections	Description
Mon, Feb 20	Chap 1-2.3	Regular languages, finite automata, nondeterminism
Wed, Feb 22		No lecture
Mon, Feb 27	Chap 2.4-3	Finite automata, regular expressions
Wed, Feb 29	Chap 3-4	Properties of regular languages
Mon, Mar 5	Chap 4.3-4.5	Decision problems, minimization of DFAs
Wed, Mar 7		No lecture
Wed, Mar 14	Chap 5.1-5.2	Context-free grammars, parse trees
Mon, Mar 19	Chap 5.3-5.4	Derivations, ambiguities
Wed, Mar 21		No lecture
Mon, Mar 26	Chap 6	Push-down automata
Wed, Mar 28	Chap 7.1-7.2	More PDA, Normal forms
Mon, Apr 2	Chap 7.3-7,4	decision problems
Wed, Apr 4	Chap 7.3-7,4	CLF properties
Mon, Apr 23	revision	Revision of context-free languages
Mon, Apr 30	Chap 8	Turing machines
Wed, May 2	Chap 8	Turing machines (continued)
Mon, May 7	Chap 9	Undecidability
Wed, May 9	Chap 9	Undecidability (continued)
Mon, May 14	Chap 10	Intractible problems
Wed, May 16	Chap 10	Intractible problems (continued)
Mon, May 21	Chap 10-11	Complexity theory
Wed, May 23	Chap 10-11	Complexity theory (continued)
Mon, May 28	revision	Revision of computability and complexity
Wed, May 30		No lecture