News:

  • Final Exam Monday June 6, 17.40 Canberra time. More on Wattle.
  • Assignment 3 released and published under assessments.
  • Assignment 2 released and is published under assessments.
  • Drop in Session every Friday, 15.00 - 16.00, HN 2.41

Content

This course (offered in semester 1 in even years) covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include: regular and context-free languages; finite automata and pushdown automata; Turing machines; Church’s thesis; computability - halting problem, solvable and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness. At successful completion of the course, students should have a good knowledge of formal computation and its relationship to languages, be able to classify formal languages into their types, be able to formally reason about languages, and understand the basic concepts of computability and complexity theory.

If you’re stuck, then you can reach out for help anytime—the course help page or course forum is a good place to start.

bars search times arrow-up