Foundations of Computing

6 unitsSem 2In Person

School of Computing · ANU College of Systems and Society

About this course

This course presents some formal notations that are commonly used for the description of computation and of computing systems, for the specification of software and for mathematically rigorous arguments about program properties. The following areas of study constitute the backbone of the course. Predicate calculus and natural deduction, inductive definitions of data types as a basis for recursive functions and structural induction, formal language theory (particularly regular expressions, finite state machines and context-free grammars), and specification languages.

Learning outcomes

1Apply the concepts of standard mathematical logic to produce proofs or refutations of well-formed propositions or arguments phrased in English or in a variety of formal notations (first order logic, discrete mathematics or Hoare logic). Express problems, presented in English, in these formal notations and demonstrate an awareness of the differences between them.
2Relate structural induction to other forms of mathematical induction, and write a recursive definition of a given simple operation on data of a given type presented via an inductive definition of the data structure.
3Explain the concept of program correctness and prove simple programs correct using Hoare Logic.
4Understand, analyse, and describe formal languages in a variety of representations including grammars and automata and Turing machines.
5Apply standard concepts of computability and complexity theory to classify computational problems.

Assessment

Weights and hurdle requirements come straight from the imported ANU record.

Assignments

Learning outcomes 1, 2, 3, 4, 5

40%

Quizzes

Learning outcomes 1, 2, 3, 4, 5

10%

Final Exam

Learning outcomes 1, 2, 3, 4, 5

50%

Study expectations

Study information

Lectures, tutorials and self-directed study to a total of 130 hours. Other Information Webpage of Foundations of Computing (COMP1600 / COMP6260)

Texts and reading

None Preliminary Reading Webpage of Foundations of Computing (COMP1600 / COMP6260), section on reading material.

Related courses

COMP1600

Related ANU course

Co taught

Course essentials

Academic year: 2026
Course subject: COMP
Subject name: Computer Science
Academic career: PGRD
School: School of Computing
College: ANU College of Systems and Society
Convener: Dr Michael Norrish
Delivery: In Person
Unit value: 6 units
EFTSL: 0.125
Last source update: Not listed

View the ANU course source

Fees

Domestic fee paying students: Domestic · 2026 · Course basis; $5,520
International fee paying students: International · 2026 · Course basis; $7,020
Student Contribution Band Code 2: Commonwealth supported · 2026; ANU contribution-band code 2

Areas and attributes

Areas of interest

Computer ScienceMathematicsInformation TechnologyAlgorithms and DataComputational Foundations