Theory of Computation

6 unitsSem 1In Person

School of Computing · ANU College of Systems and Society

About this course

This course covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include the following: regular and context-free languages; finite automata and pushdown automata; Turing machines; computability - halting problem, solvable, and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness.

Learning outcomes

1Demonstrate advanced knowledge of formal computation and its relationship to languages
2Distinguish different computing languages and classify their respective types
3Recognise and comprehend formal reasoning about languages
4Demonstrate a competent understanding of the basic concepts of complexity theory

Assessment

Weights and hurdle requirements come straight from the imported ANU record.

Assignments, quizzes, in-class activities

Learning outcomes 1, 2, 3, 4

50%

Final Exam and/or during semester assessments

Learning outcomes 1, 2, 3, 4

50%

Study expectations

Study information

Lectures, tutorials, assignments, self-study & exam prep for a total of 130 hours. Other Information COMP3630 Website

Texts and reading

See COMP3630 Resources

Related courses

COMP6363

Related ANU course

Co taught

Course essentials

Academic year: 2026
Course subject: COMP
Subject name: Computer Science
Academic career: UGRD
School: School of Computing
College: ANU College of Systems and Society
Convener: Dr Pascal Bercher
Delivery: In Person
Unit value: 6 units
EFTSL: 0.125
Last source update: Not listed

View the ANU course source

Fees

Domestic fee paying students: Domestic · 2026 · Course basis; $5,520
International fee paying students: International · 2026 · Course basis; $7,020
Student Contribution Band Code 2: Commonwealth supported · 2026; ANU contribution-band code 2

Areas and attributes

Areas of interest

Computer ScienceAdvanced ComputingComputational Foundations