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

Pre-2019 Handbook Editions

Access past handbook editions (2018 and prior)