Computational and Algorithmic Thinking

The Computational and Algorithmic Thinking (CAT) competition, formerly known as the
Australian Informatics Competition (AIC), is a pre-programming competition taken annually
by more than 7000 school students from Australia, New Zealand and a number of other Asia-
Pacific countries. It is run by the Australian Informatics Olympiad Committee (AIOC) and
is intended to serve a number of purposes. Firstly, it introduces students and their teachers
to algorithmic thinking, now a required component of the Australian Curriculum, through
engaging problems without the need for programming skills. Secondly, it identifies students
with the capacity to program and points them towards resources through which they can
pursue this, and to further competitions which they can enter with a view to developing their
programming skills. Finally, it is the first in a series of events that identify students who will
represent Australia at the annual International Olympiad in Informatics (IOI). (The term
informatics is used in Europe as a synonym for computer science.)
The CAT has traditionally been a pen and paper competition, but in 2014 a decision was
made to introduce an online version of the competition from 2015. In addition, a further
division of the competition was introduced for Upper Primary students (Years 5 and 6). The
questions in the CAT are designed to be quick to solve and highly approachable, and range
in difficulty from very easy to challenging. The contest employs a mixture of multiple-choice
and integer answers, and incorporates unique ‘three-stage tasks’ that encourage students to
develop informal algorithms and apply them to test data of increasing size.
The multiple-choice questions can be classified into four broad categories:
applying the rules questions, that ask students to apply a well-defined set of rules to
given data
logic questions, that use non-algorithmic puzzles to encourage rigorous reasoning and
case analysis
analysis questions, where students are asked to understand the behaviour of an algo-
rithm that solves a given problem
algorithm questions, that encourage students to develop an informal algorithm to solve
a given puzzle.
Explanations of these categories and their relevance are given in the ‘Solutions’ section of
this book.
The integer answer questions are typically algorithmic. Students must devise and follow some
repeated systematic procedure. For each question the students are given three sets of data
of increasing size. These questions are explicitly designed to entice students into formulating
algorithms. The first data set is often small enough to be solved by ad hoc techniques. By the
second, students should have a feel for the problem and be developing systematic procedures
for solving the problem. These procedures can then be applied to the third data set.
Algorithmic and analysis questions are often variations on well-known classes of problems
such as shortest path problems (algorithm questions) and searching algorithms (analysis
questions), and some students may have already encountered them. Other questions are not
standard and students have to devise algorithms from the context of the problem.
The ‘Questions’ section of the book presents the questions, organised by category and prob-
lem type. The ‘Solutions’ section gives the solutions and answers. Each category is given a
general introduction, describing its relevance to information technology in general and pro-
gramming in particular. Each problem type also has an introduction, including the practical
applications of the problem type and an outline of the method of solution.
Algorithmic Thinking and the Australian Curriculum
The Australian Curriculum has been developed over the last few years and is being adopted by
all states and territories with implementation F – 10 scheduled to be complete by 2018. In the
Technologies learning area of the Curriculum, there are two distinct but related subjects, one
of which is Digital Technologies. For many teachers, the content of this subject will present
quite a challenge, as it requires them to teach algorithmic thinking from the Foundation year
and to introduce coding from as early as Year 3. Previously, this has been the preserve of a
small number of courses in the senior years of the curriculum, but there is a worldwide demand
for greater coding skills as a part of core education; Australia is not alone in promoting this
type of thinking as a part of the compulsory curriculum. Victoria has taken a further initiative
and included algorithmic thinking as a part of the mathematics curriculum. Other states are
also looking at how this implementation will work in practice and who can best deliver the
algorithmic content.
There is a rapidly growing variety of resources to teach various different programming lan-
guages, but there is little point in learning a programming language without a good under-
standing of the algorithmic thinking which sits behind any purposeful computer program. In
addition to providing many questions which promote this type of thinking, this book contains
a background chapter on what an algorithm is and explores how questions can be analysed
from an algorithmic perspective. We would prefer that teachers did not think of algorithmic
thinking as yet another thing which they have to teach, but rather as a pedagogical approach
to problem solving in general, a skill which will be transferable across many disciplines.