Skip navigation
The Australian National University
Theory of Computation COMP3630/COMP6363

Theory of Computation COMP3630/COMP6363


  • Practice Exam [.pdf], Second Practice Exam [.pdf]
  • Exam Dropin: Monday, June 15 2020, 12.00 noon. Details on Piazza.
  • Assignment 3 released.
  • Assignment 3 submission due on June 2, 2020 as the original due date (June 1) is a public holiday in the ACT.
  • Typo in Assignment 2 corrected.
  • We have corrected one typo in the assignment sheet, and have added an explanatory sentence in the last question.
  • Assignment 1 is out now and is posted in the assignments section
  • Instructions for online tutorials under Online in the side bar.
  • Tutorial sheet for week 2 now online under Tutorials
  • Timetable change: Monday's lecture in Marie Reay 6.02 (not 2.02).

COMP3630/6363 goes Online

Following the closure of the ANU campus, we are working hard to move all the content online. Specifically for this course, we are starting with the following setup that we're continuously reviewing:
  • We continue to run two online tutorials that are open for all participants of the course. We are monitoring demand and attendance, and wil open new slots as needed. Details under Online in the side bar.
  • Lectures are delivered in terms of pre-recorded snippets published under Schedule in the side bar.
  • We are in the process of scheduling two additional Q&A sessions, one for lectures and the other one for tutorials.
  • Assignment submission is pushed back by one week due to the interruption in teching.

Weekly Survival Guide

Here's what we suggest you do each week:
  • Watch the week's videos that are linked from the Schedule page, and read the corresponding chapters in the textbook
  • Attempt the tutorial exercises for the week that hang off the Tutorials page.
  • Tune in to one of the Online Labs.
  • If there are things that you'd like to know more about, but that weren't covered, join a Q&A session as described in the Online page.
  • Make use of the Piazza forum. If you have a question, it's likely that at least 10 of your classmates have the same quetion.
  • Keep an eye on the Assignments Schedule


This course (offered in semester 1 in even years) covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include: regular and context-free languages; finite automata and pushdown automata; Turing machines; Church's thesis; computability - halting problem, solvable and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness. At successful completion of the course, students should have a good knowledge of formal computation and its relationship to languages, be able to classify formal languages into their types, be able to formally reason about languages, and understand the basic concepts of computability and complexity theory.

Offered By: The Research School of Computer Science @ Australian National University
Offered In:Semester 1, 2020 (24 February to 30 May). Lecturer: Dirk Pattinsonr (Convenor)
Tutors: tbd
Target: Undergraduate (COMP3630) and Graduate (COMP6363) students. Others welcome.
Enrollment: Undergraduate & Masters: The usual way via ISIS. Honors&Others: Contact admin/lecturer.
Admin: CECS student services Class representative: tbd, see here for further information
Course Subject: Computer Science
Unit Value: 6 units
Indicative Workload: 24h lectures, 11h tutorials, ~3×15h assignm., ~40h self-study, +exam prep.

Quick links: [Home] [Timetable] [Schedule] [Tutorials] [Piazza Forum] [Assignments] [Resources] [Prerequisites] [Assessment]

Updated:  15 June 2020 / Responsible Officer:   JavaScript must be enabled to display this email address. / Page Contact:   JavaScript must be enabled to display this email address. / Powered by: Snorkel 1.4