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.

v

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.