Irish Leaving Certificate Computer Science

Computational thinking is a way of solving problems so that the solution can be carried out by a computer, or by a person following the same steps exactly. It is not programming itself. It is the thinking that comes first, and a program is one way of writing the result down. The same thinking is used when planning a timetable, sorting post or working out the quickest route through a city.

A systematic process for solving problems

A systematic process is one that can be described, repeated and checked, so two people following it reach the same answer. Computational thinking usually works through these stages.

1. State the problem precisely: what is given (the inputs), what must be produced (the outputs) and what conditions apply.
2. Break the problem into smaller problems that can each be solved on their own.
3. Look for patterns, including similarities with problems already solved.
4. Decide what detail matters and ignore the rest.
5. Write the steps of a solution as an algorithm.
6. Test the algorithm on examples, including awkward ones, and improve it.

The stages are not passed through once. A test in the last step often shows that the problem was stated loosely, so the work returns to an earlier stage. Solving a problem in this repeated way is called an iterative approach.

Decomposition

Decomposition means breaking a problem into smaller units, each simple enough to solve and to test by itself. The smaller units are then combined. Decomposing again at each level, until every piece is easy, is what "systematic" adds.

Suppose a school wants a program that works out each class's average mark and prints a ranked list. One decomposition is:

• read the marks for every student in a class
• calculate the average for one class
• repeat that for every class
• sort the classes by average, highest first
• print the ranked list

Each part can be written, tested and changed without disturbing the others. The part that calculates an average is also the same whichever class it is applied to, which leads to the next idea.

Pattern recognition

Pattern recognition is noticing that parts of a problem, or different problems, share a structure. Totalling the marks of a class and totalling the prices in a shopping basket are the same pattern: start at zero, go through the items, add each one. Once a pattern is recognised, one solution serves every case, so the pattern is written once as a function and used again. Patterns also show up in data, where a rise each summer or a repeated sequence of clicks can be used to make predictions.

Abstraction

Abstraction means leaving out the detail that does not matter for the problem, so that what is left can be reasoned about. A map of a railway network shows stations and the lines between them and leaves out the real distances and the shape of the track, because a passenger planning a trip only needs to know what connects to what. Abstraction is treated in detail in its own note; here it is the stage where the problem is reduced to the facts the solution actually uses.

Algorithmic thinking

An algorithm is a finite sequence of unambiguous steps that solves a problem or carries out a task. It must end, and each step must be clear enough to be carried out without judgement. Every algorithm is built from three constructs:

• sequence, where steps run one after another in order
• selection, where a condition decides which steps run
• iteration, where steps repeat while a condition holds or a set number of times

An algorithm for finding the largest of a list of numbers shows all three. Take the first number as the largest so far; then, for each remaining number, if it is larger than the largest so far, it becomes the new largest; when the numbers run out, report the largest.

def largest(numbers):
    best = numbers[0]
    for n in numbers[1:]:
        if n > best:
            best = n
    return best

print(largest([14, 3, 27, 8, 19]))   # 27

The same steps can be written as plain sentences, as pseudocode or as Python. The algorithm is the same in each form, and the choice of form depends on who will read it.

Choosing between solutions

A problem usually has more than one solution, and they can be compared on several grounds.

Two solutions to finding a name in a sorted list of a million names show the trade-off. Checking each name in turn is simple and works on any list, but may need a million comparisons. Halving the list repeatedly needs at most twenty comparisons, because $2^{20} = 1\,048\,576$, but it only works when the list is sorted and the code is harder to write correctly. Which is better depends on how often the search runs and whether the list is already sorted.

Computational thinking beyond programming

The same stages apply away from a keyboard. A shop deciding how to arrange its shelves decomposes the store into sections, spots that the busiest sections share a pattern of what is bought together, abstracts away the colour of the packaging, and tests a layout before adopting it. The feature that marks the thinking as computational is that the result is precise enough to be automated: the steps can be handed to a machine that will follow them exactly, as often as needed and far faster than a person could.