Assignments (30%); Final Exam (70%)
The ANU uses Turnitin to enhance student citation and referencing techniques, and to assess assignment submissions as a component of the University's approach to managing Academic Integrity. While the use of Turnitin is not mandatory, the ANU highly recommends Turnitin is used by both teaching staff and students. For additional information regarding Turnitin please visit the ANU Online website.
Workload25h lectures, 12h tutorials, approx. 3×15h assignments, approx. 40h self-study, +exam prep.
Requisite and Incompatibility
To enrol in this course you must have completed (COMP1110 or COMP1140) and (COMP1600 or COMP2600). Incompatible with COMP6363.
Hopcropft, J.E., Motwani, R. & Ullman, J.D.Automata Theory, Languages, and Computation 3rd edition, Pearson Education, 2007.
Indicative Reading List
M. Sipser (2012) Introduction to the Theory of Computation (alternative to [HMU06])
S. Aaronson (2005) NP-complete Problems and Physical Reality
S. Arora and B. Barak (2009) Computational Complexity: A Modern Approach
View Specification Document | Reading List
Theory of Computation (H) COMPSCI4072
- Academic Session: 2017-18
- School: School of Computing Science
- Credits: 10
- Level: Level 4 (SCQF level 10)
- Typically Offered: Semester 2
- Available to Visiting Students: Yes
- Available to Erasmus Students: Yes
This course covers the theory of sequential, concurrent and quantum computation. The main topics are: formal language theory and the connection to automata; lambda calculus as a foundation for functional computation; pi calculus as a foundation for concurrent computation; the theory of operational semantics and type systems; principles of quantum computation.
2 hours of lecture time and 1 hour of tutorial or practical work per week
Requirements of Entry
Algorithmics I (H) (or equivalent)
80% for the end of year exam
20% for assessed coursework, which is likely to be separated into two or three smaller assignments
The assessed coursework will assess ILOs 4, 7 and 10 as well as touching on other ILOs.
The exam will assess ILOs 1, 2, 3, 5, 6, 8 and 9.
Main Assessment In: April/May
Are reassessment opportunities available for all summative assessments? No
Reassessments are normally available for all courses, except those which contribute to the Honours classification. For non-Honours courses, students are offered reassessment in all or any of the components of assessment if the satisfactory (threshold) grade for the overall course is not achieved at the first attempt. This is normally grade D3 for undergraduate students and grade C3 for postgraduate students. Exceptionally it may not be possible to offer reassessment of some coursework items, in which case the mark achieved at the first attempt will be counted towards the final course grade. Any such exceptions for this course are described below.
The nature of the coursework is such that it takes a significant number of days to produce it and this effort is infeasible for supporting the re-doing of such coursework over the summer.
The aim of the course is to show how several models of computation can be formally defined in order to give a rigorous foundation for sequential, concurrent and quantum programming paradigms.
Intended Learning Outcomes of Course
By the end of this course students will be able to:
1. Explain the connection between formal languages and automata in terms of the Chomsky hierarchy;
2. Evaluate expressions in lambda calculus according to the definition of the reduction relation;
3. Determine whether or not expressions in lambda calculus are typable in the simple type system;
4. Implement lambda calculus expressions in a functional language such as Haskell or ML, or the functional fragment of Python;
5. Execute pi calculus processes according to the definition of the reduction relation, and determine bisimulation relationships between processes;
6. Determine whether or not processes in pi calculus are typable in the simple type system;
7. Implement pi calculus processes in a simulation environment or in an appropriate fragment of the Go programming language;
8. Explain the principles of quantum computation and the characteristics that distinguish it from classical computation;
9. Calculate the effect of quantum protocols and algorithms according to the laws of Hilbert spaces;
10. Implement and analyse quantum protocols and algorithms in a suitable simulation environment.
Minimum Requirement for Award of Credits
Students must submit at least 75% by weight of the components (including examinations) of the course's summative assessment.