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: MATH1081, and COMP1927 or COMP2521
Delivery
In-person - Standard (usually weekly or fortnightly)
Course Outline
To access course outline please visit below link (Please note that access to UNSW Canberra course outlines requires VPN):
Fees
Type | Amount |
---|---|
Commonwealth Supported Students (if applicable) | $994 |
Domestic Students | $5970 |
International Students | $5970 |
Pre-2019 Handbook Editions
Access past handbook editions (2018 and prior)