Computer Science COMP3630/COMP6363
Theory of Computation
Lectures
| Room |
Day |
Time |
| Han 2.24 (Building 43) |
Monday |
12:00-14:00 |
| Han 2.24 (Building 43) |
Friday |
1:00-3:00 |
Timetabling
Updated lecture times and place above. There will be recording
facilities in the new lecture room.
Lecture Notes
Almost all of the
course content can be found in the textbook. Lecture notes will not
be made available in general.
Tutorials
There will not be separate tutorials for this course.
Some of the lectures will be run in tutorial mode. The lecturers
will provide weekly tutorial sheets containing both self-test
questions with solutions on the web and early-release assignment
questions.
- Tutorial 1 [.pdf]
- Tutorial 2 [.pdf]
(updated Fri Mar 8 11:41:53 EST 2013: formal definition of S(L))
- Tutorial 3 [.pdf]
- Tutorial 4 [.pdf]
- Tutorial 5 [.pdf]
- Tutorial 6 [.pdf]
- Tutorial 7 [.pdf]
- Tutorial 8 [.pdf]
- Tutorial 9 [.pdf]
Assessment Scheme
The course will have 3 assignment of equal weight totalling
30%, and one written exam of weight 70%.
Assessment Schedule
- Assignment 1 [.pdf],
(updated Fri Mar 8 11:41:53 EST 2013: formal definition of S(L))
- Out: Fri Mar 8. Due: Fri Mar 22
- Feedback, Hints and Pitfalls
[.pdf]
- Assignment 2 [.pdf]
- Out: Mon Apr 15. Due: 27. Due: Mon Apr 29
- Feedback, Hints and Pitfalls
[.pdf]
- Assignment 3 [.pdf]
- Out: Mon May 6. Due: Fri May 17
- Feedback, Hints and Pitfalls
[.pdf]
Textbook
J. E. Hopcropft, R. Motwani, J. D. Ullman,
Automata Theory, Languages, and Computation.
3rd edition, Pearson Eduction, 2008.
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
Jinbo Huang
Room B252, RSISE Building 115
jinbo.huang(at)rsise.anu.edu.au
Dirk Pattinson (course coordinator)
Romm B231, RSIE Building 115
6125 8612; dirk.pattinson(at)anu.edu.au
Lecture schedule
This schedule is a guide that will be updated during the semester.
| Date |
Book sections | Description |
| Mon, Feb 18 |
Chap 2.1-2.2 | Regular languages, finite automata |
| Tue, Feb 19 |
Chap 2.3-2.5 | Nondeterminism and epsilon-transitions |
| Mon, Feb 25 |
Chap 3.1-3.2 | Regular expressions and finite automata |
| Fri, Mar 1 |
Chap 3.3-3.4 | Applications and algebraic laws |
| Mon, Mar 4 |
Chap 4 | Properties of regular languages |
| Fri, Mar 8 |
| (continued) |
| Mon, Mar 11 |
Public Holiday |
| Fri, Mar 15 |
Chap 5 | Context free grammars |
| Mon, Mar 18 |
Chap 6 | Pushdown automata |
| Fri, Mar 22 |
| (continued) |
| Mon, Mar 25 |
Chap 7 | Properties of context-free languages |
| Fri, Mar 29 |
Public Holiday |
| Teaching Break Mon Apr 1 - Fri Apr 12 |
| Mon, Apr 15 |
| (continued) |
| Fri, Apr 19 |
Chap 8 | Turning Machines |
| Mon, Apr 22 |
| (continued) |
| Fri, Apr 26 |
Chap 9 | Undecidability |
| Mon, Apr 29 |
| (continued) |
| Fri, May 39 |
Chap 10 | Intractable problems |
| Mon, May 6 |
| (continued) |
| Fri, May 10 |
Chap 11 | Additional classes |
| Mon, May 13 |
| (continued) |
| only revision lectures after May 13 |
Handouts
(will be made avaliable here)
Past Exam Papers
|
