Course coordinator
Dr Kasra Khosoussi
Course overview
- Study period
- Semester 1, 2026 (23/02/2026 - 20/06/2026)
- Study level
- Undergraduate
- Location
- St Lucia
- Attendance mode
- In Person
- Units
- 2
- Administrative campus
- St Lucia
- Coordinating unit
- Elec Engineering & Comp Science School
This course provides a rigorous introduction to the Theory of Computation, exploring the fundamental limits of what can be computed and how efficiently computational problems can be solved. Students study formal models of computation through the framework of languages and automata, including deterministic and nondeterministic finite automata (DFA and NFA), pushdown automata (PDA), and Turing machines. The course emphasizes precise mathematical reasoning and proof techniques, and examines fundamental questions of decidability and undecidability. Additionally, the course covers an introduction to Computational Complexity Theory as the study of the resources required to solve computational problems. The course delves into central complexity classes, including P and NP, and explores the practical limits of efficient computation. The course also introduces alternative models of computation, including an introduction to quantum computing, to provide a broader perspective beyond the classical model.
In this course, we will explore:
- How to formalize computational problems
- What it means for a problem to be computable, and the fundamental limits of algorithmic problem solving
- How simple abstract machines give rise to powerful models of computation
- Why some problems are undecidable, and how to formally prove such impossibility results
- How computational problems are classified by the resources required to solve them, such as time and space
- The significance of the complexity classes P and NP, and what the P vs. NP question means
- How different models of computation (e.g., quantum computing) expand our understanding of what computation can be
Course requirements
Assumed background
This course assumes that students have some basic knowledge of Python programming and are familiar with concepts covered in Discrete Mathematics (e.g., sets, functions and relations, graphs, boolean operations, etc).
Prerequisites
You'll need to complete the following courses before enrolling in this one:
(MATH1061 or MATH1081) and (CSSE1001 or ENGG1001)
Course contact
Course staff
Lecturer
Dr Kasra Khosoussi
Dr Josh Arnold
Guest lecturer
Dr Riddhi Gupta
Timetable
The timetable for this course is available on the UQ Public Timetable.
Additional timetable information
Lectures will be running all weeks from Week 1 to Week 13 (inclusive).
Applied Classes will be running each week from Week 2 to Week 13 (inclusive).
Practical Classes will be running from Week 10 to Week 13 (inclusive).
Aims and outcomes
The aim of this course is to provide a modern introduction to the Theory of Computation by:
- Presenting the main models of computation, including finite automata, pushdown automata, and Turing machines
- Developing both practical and theoretical understanding of these models, their expressive power, and their relationships to one another
- Examining fundamental limits of computation through the study of decidability, undecidability
- Introducing computational complexity as the study of computation under limited resources, including an exploration of the classes P and NP
- Introducing alternative and emerging models of computation, including an introduction to quantum computation
Learning outcomes
After successfully completing this course you should be able to:
LO1.
Define core concepts in the theory of computation, including computation, algorithms, decision problems, and formal languages.
LO2.
Construct formal models of computation using finite automata, pushdown automata, and Turing machines.
LO3.
Analyze the expressive power and limitations of different computational models.
LO4.
Apply formal proof techniques to establish correctness, equivalence, and impossibility results.
LO5.
Determine the decidability or undecidability of computational problems using appropriate theoretical tools.
LO6.
Explain computational complexity in terms of resource usage such as time and space.
LO7.
Classify computational problems within basic complexity classes, including P and NP.
LO8.
Describe the principles of quantum computation and explain how quantum models differ from classical models of computation.
Assessment
Assessment summary
| Category | Assessment task | Weight | Due date |
|---|---|---|---|
| Tutorial/ Problem Set |
Assignment 1
|
20% |
27/03/2026 4:00 pm |
| Computer Code, Tutorial/ Problem Set |
Assignment 2
|
20% |
1/05/2026 4:00 pm |
| Computer Code, Tutorial/ Problem Set |
Assignment 3
|
20% |
29/05/2026 4:00 pm |
| Examination |
Final Examination
|
40% |
End of Semester Exam Period 6/06/2026 - 20/06/2026 |
A hurdle is an assessment requirement that must be satisfied in order to receive a specific grade for the course. Check the assessment details for more information about hurdle requirements.
Assessment details
Assignment 1
- Hurdle
- Mode
- Activity/ Performance, Written
- Category
- Tutorial/ Problem Set
- Weight
- 20%
- Due date
27/03/2026 4:00 pm
- Learning outcomes
- L01, L02, L03, L04
Task description
A problem set assignment focused on Finite Automata covered in weeks 1-3 of the course.
This task has been designed to be challenging, authentic and complex. Whilst students may use AI and/or MT technologies, successful completion of assessment in this course will require students to critically engage in specific contexts and tasks for which artificial intelligence will provide only limited support and guidance. A failure to reference generative AI or MT use may constitute student misconduct under the Student Code of Conduct. To pass this assessment, students will be required to demonstrate detailed comprehension of their written submission independent of AI and MT tools.
To verify individual understanding, teaching staff may randomly select a number of students for a brief interview to explain and demonstrate their solutions.
Hurdle requirements
There are grade hurdles associated with this practical -- please see the Course grading section for details and additional requirements. To be eligible for a Grade of 6 or 7, students must achieve at least 50% on all 3 Assignments. To be eligible for a Grade of 4 or 5, students must achieve at least 50% on 2 (out of 3) Assignments. (See Course grading section for additional requirements).Submission guidelines
Online submission by the due date (27/03/2026, 4:00pm AEST) -- please refer to the assignment task sheet for further details.
Deferral or extension
You may be able to apply for an extension.
The maximum extension allowed is 3 days. Extensions are given in multiples of 24 hours.
Extensions are limited to 3 days as feedback will be provided within 10 days.
Late submission
A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.
Assignment 2
- Hurdle
- Mode
- Activity/ Performance, Written
- Category
- Computer Code, Tutorial/ Problem Set
- Weight
- 20%
- Due date
1/05/2026 4:00 pm
- Learning outcomes
- L02, L03, L04, L05
Task description
A problem set assignment focused on Pushdown Automata, Turing Machines, Cellular Automata, and Decidability covered in weeks 4-7 of the course.
This task has been designed to be challenging, authentic and complex. Whilst students may use AI and/or MT technologies, successful completion of assessment in this course will require students to critically engage in specific contexts and tasks for which artificial intelligence will provide only limited support and guidance. A failure to reference generative AI or MT use may constitute student misconduct under the Student Code of Conduct. To pass this assessment, students will be required to demonstrate detailed comprehension of their written submission independent of AI and MT tools.
To verify individual understanding, teaching staff may randomly select a number of students for a brief interview to explain and demonstrate their solutions.
Hurdle requirements
There are grade hurdles associated with this practical -- please see the Course grading section for details and additional requirements. To be eligible for a Grade of 6 or 7, students must achieve at least 50% on all 3 Assignments. To be eligible for a Grade of 4 or 5, students must achieve at least 50% on 2 (out of 3) Assignments. (See Course grading section for additional requirements).Submission guidelines
Online submission by the due date (1/05/2026, 4:00pm AEST) -- please refer to the assignment task sheet for further details.
Deferral or extension
You may be able to apply for an extension.
The maximum extension allowed is 3 days. Extensions are given in multiples of 24 hours.
Extensions are limited to 3 days as feedback will be provided within 10 days.
Late submission
A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.
Assignment 3
- Hurdle
- Mode
- Activity/ Performance, Written
- Category
- Computer Code, Tutorial/ Problem Set
- Weight
- 20%
- Due date
29/05/2026 4:00 pm
- Learning outcomes
- L04, L05, L06, L07, L08
Task description
A problem set and coding assignment focused on Complexity Theory and Quantum Computing covered in weeks 8-12 of the course.
This task has been designed to be challenging, authentic and complex. Whilst students may use AI and/or MT technologies, successful completion of assessment in this course will require students to critically engage in specific contexts and tasks for which artificial intelligence will provide only limited support and guidance. A failure to reference generative AI or MT use may constitute student misconduct under the Student Code of Conduct. To pass this assessment, students will be required to demonstrate detailed comprehension of their written submission independent of AI and MT tools.
To verify individual understanding, teaching staff may randomly select a number of students for a brief interview to explain and demonstrate their solutions.
Hurdle requirements
There are grade hurdles associated with this practical -- please see the Course grading section for details and additional requirements. To be eligible for a Grade of 6 or 7, students must achieve at least 50% on all 3 Assignments. To be eligible for a Grade of 4 or 5, students must achieve at least 50% on 2 (out of 3) Assignments. (See Course grading section for additional requirements).Submission guidelines
Online submission by the due date (29/05/2026, 4:00pm AEST) -- please refer to the assignment task sheet for further details.
Deferral or extension
You may be able to apply for an extension.
The maximum extension allowed is 3 days. Extensions are given in multiples of 24 hours.
Extensions are limited to 3 days as feedback will be provided within 10 days.
Late submission
A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.
Final Examination
- Hurdle
- Identity Verified
- In-person
- Mode
- Written
- Category
- Examination
- Weight
- 40%
- Due date
End of Semester Exam Period
6/06/2026 - 20/06/2026
- Other conditions
- Secure.
- Learning outcomes
- L01, L02, L03, L04, L05, L06, L07, L08
Task description
A 120-minute examination will be held during the examination period. Students will sit an on-campus invigilated exam.
The exam will cover content from the whole semester.
This assessment item is to be completed in-person. The use of Artificial Intelligence (AI) tools will not be permitted. Any attempted use of AI may constitute student misconduct under the Student Code of Conduct.
Hurdle requirements
There are grade hurdles associated with the final exam -- please see the Course grading section for details and additional requirements.Exam details
| Planning time | 10 minutes |
|---|---|
| Duration | 120 minutes |
| Calculator options | (In person) Casio FX82 series only or UQ approved and labelled calculator |
| Open/closed book | Closed book examination - no written materials permitted |
| Exam platform | Paper based |
| Invigilation | Invigilated in person |
Submission guidelines
Deferral or extension
You may be able to defer this exam.
Course grading
Full criteria for each grade is available in the Assessment Procedure.
| Grade | Description |
|---|---|
| 1 (Low Fail) |
Absence of evidence of achievement of course learning outcomes. Course grade description: A Grade of 1 will be awarded for an overall mark below 20%. |
| 2 (Fail) |
Minimal evidence of achievement of course learning outcomes. Course grade description: A Grade of 2 will be awarded for an overall mark below 47% but greater than or equal to 20%. |
| 3 (Marginal Fail) |
Demonstrated evidence of developing achievement of course learning outcomes Course grade description: A Grade of 3 will be awarded for an overall mark below 50% but greater than or equal to 47%, while also not meeting the requirements for higher grades. |
| 4 (Pass) |
Demonstrated evidence of functional achievement of course learning outcomes. Course grade description: A Grade of 4 will be awarded for an overall mark below 65% but greater than or equal to 50%, passed at least 2 out of 3 main assignments and at least 40% on the final exam. |
| 5 (Credit) |
Demonstrated evidence of proficient achievement of course learning outcomes. Course grade description: A Grade of 5 will be awarded for an overall mark below 75% but greater than or equal to 65%, passed at least 2 out of 3 main assignments and passed the final exam. |
| 6 (Distinction) |
Demonstrated evidence of advanced achievement of course learning outcomes. Course grade description: A Grade of 6 will be awarded for an overall mark below 85% but greater than or equal to 75%, completed and passed all 3 main assignments and obtained greater than or equal to 75% on the final exam. |
| 7 (High Distinction) |
Demonstrated evidence of exceptional achievement of course learning outcomes. Course grade description: A Grade of 7 will be awarded for an overall mark of 85% or greater, completed and passed all 3 main assignments and obtained greater than or equal to 85% on the final exam. |
Additional course grading information
Note that 'passing' assessments is defined as obtaining 50% or more on that assessment. Marks will be rounded up for computing the grade hurdles and the final grade.
Supplementary assessment
Supplementary assessment is available for this course.
Additional assessment information
Having Troubles?
If you are having difficulties with any aspect of the course material, you should seek help and speak to the course teaching staff. If external circumstances are affecting your ability to work on the course, you should seek help as soon as possible. The University and UQ Union have organisations and staff who are able to help; for example, UQ Student Services are able to help with study and exam skills, tertiary learning skills, writing skills, financial assistance, personal issues, and disability services (among other things). Complaints and criticisms should be directed in the first instance to the course coordinator. If you are not satisfied with the outcome, you may bring the matter to the attention of the School of EECS Director of Teaching and Learning.
Learning resources
You'll need the following resources to successfully complete the course. We've indicated below if you need a personal copy of the reading materials or your own item.
Library resources
Find the required and recommended resources for this course on the UQ Library website.
Additional learning resources information
Dr. Chandra will provide a draft of his book on the subject to be freely provided and used during the course. Dr. Chandra also has created a ComputationﾠYouTubeﾠPlaylist of the covered topics.
Learning activities
The learning activities for this course are outlined below. Learn more about the learning outcomes that apply to this course.
Filter activity type by
Please select
| Learning period | Activity type | Topic |
|---|---|---|
Multiple weeks |
Not Timetabled |
Videos and Reading Videos and reading materials may be provided for topics necessary and of interest to the course. It is expected that students spend a good amount of time studying these recommended materials. Learning outcomes: L01, L02, L03, L04, L05, L06, L07, L08 |
Multiple weeks From Week 1 To Week 13 |
Lecture |
Lecture Sessions Course topics covered in a series of lectures. The lecturers may suggest a reading list (from suggested resources available freely via UQ Library) for each week. Learning outcomes: L01, L02, L03, L04, L05, L06, L07, L08 |
Multiple weeks From Week 2 To Week 13 |
Applied Class |
Applied Class These sessions are designed to support students’ understanding of course material and problem-solving techniques. During these sessions, the teaching staff may:
The students will be able to get feedback prior to the census date during Applied Classes. Learning outcomes: L01, L02, L03, L04, L05, L06, L07, L08 |
Multiple weeks From Week 10 To Week 13 |
Practical |
Practical Class During these sessions, teaching staff may provide additional guidance and support for Assignment 3. Learning outcomes: L06, L07, L08 |
Policies and procedures
University policies and procedures apply to all aspects of student life. As a UQ student, you must comply with University-wide and program-specific requirements, including the:
- Student Code of Conduct Policy
- Student Integrity and Misconduct Policy and Procedure
- Assessment Procedure
- Examinations Procedure
- Reasonable Adjustments for Students Policy and Procedure
- AI for Assessment Guide
Learn more about UQ policies on my.UQ and the Policy and Procedure Library.
School guidelines
Your school has additional guidelines you'll need to follow for this course: