Overview

Computability: formal languages and problems, Turing Machines (TMs), computability, (semi-)decidability, universal TMs, Church-Turing thesis, halting problem, reduction and undecidability proofs, examples; Complexity: run time, space, complexity classes, non-determinism and NP, polynomial reductions and NP completeness, optimisation problems and approximation, randomisation; Languages and Automata: regular expressions and languages, finite automata, determinisation, … For more content click the Read More button below.

Conditions for Enrolment

Prerequisite: COMP9020 and COMP9024

Delivery

Multimodal - Standard (usually weekly or fortnightly)

Please note that the above delivery information is an indication on how this course may be delivered within the year.  Delivery mode(s) for each term can be viewed on other sources such as myUNSW and class timetable site.

This Handbook is a comprehensive catalogue of our offerings and includes courses that can be taken to satisfy program requirements irrespective as to their availability for a particular year. Availability of courses is best checked using filters on this site or on the class timetable site.

Fees

TypeAmount
Commonwealth Supported Students (if applicable)$1165
Domestic Students$5490
International Students$7260

Disclaimer

Where a fee is displayed as “Not Applicable”, including some Work Experience and UNSW Canberra courses, please contact the relevant Faculty for any enquiry.

Note that the University reserves the right to vary student fees in line with relevant legislation. The fee information is provided as a guide and more specific information about fees, including policy, can be found here.

Commonwealth Supported Students:

Please refer to the information about new Student Contribution band classifications. Note that grandfathering arrangements are applicable for some cohorts of students, and other special arrangements apply for a limited number of programs. The Field of Education displayed on the right-hand side of this page may be applicable in understanding which fee rate will apply to you.

Where a Commonwealth Supported fee is displayed it does not guarantee that such places are available.

Pre-2019 Handbook Editions

Access past handbook editions (2018 and prior)
Pre-2019 Handbook Editions