The algorithmic thinking question

A question with no code

Paper 2 contains one compulsory question that focuses on algorithmic thinking without any code to read or write. It appears on the SL paper and is one of the two SL questions repeated on the HL paper, so every student answers it. The question tests whether you can design, follow and improve an algorithm without the support of a programming language, so it asks the same of you whether you studied Python or Java.

The guide says only that the question focuses on algorithmic thinking "without the need to interpret or write code". No 2027 paper is public yet, so the shapes described here are inferred from how the course frames algorithmic thinking and from earlier IB Computer Science papers. Expect a problem in a short everyday context (a ticket queue, a game rule, a sorting process with cards, a delivery route) followed by parts such as:

• work out the result by hand for given inputs;

• trace a flowchart and complete a trace table, then state the output;

• describe or construct an algorithm in numbered steps;

• identify a pattern or a rule from worked cases;

• identify a flowchart symbol or explain what part of a flowchart does;

• suggest an improvement and justify it in terms of efficiency;

• apply a computational thinking idea from subtopic B1.1, such as writing a problem specification or explaining how decomposition helps.

Answers are written in words, numbered steps, tables and diagrams. Writing Python or Java in this question is unlikely to gain anything extra, and it can cost marks if the question asks for steps a non-programmer could follow.

The four-step algorithmic thinking process

The course guide describes algorithmic thinking as four steps. They are the most reliable way to attack an unfamiliar problem in this question, and each step matches a kind of question part.

The process applied: giving change

A shop wants an algorithm that gives change using as few coins as possible. Its coins are worth 50, 20, 10, 5, 2 and 1 cents.

Steps 1 and 2, explore and record. Work several amounts by hand and write down every decision made, not only the answer.

Step 3, generalise. In every case the same thing happened: take the largest coin that is not more than the amount left, subtract it, and repeat; when the largest coin no longer fits, move to the next smaller coin; stop when nothing is left. Written as numbered steps:

1. Input the amount.

2. Set the coin to the largest value, 50.

3. While the amount is greater than 0, repeat steps 4 and 5.

4. If the coin is less than or equal to the amount, output the coin and subtract it from the amount.

5. Otherwise, set the coin to the next smaller value.

6. Stop.

Step 4, test and validate. An amount of 0 outputs nothing, which is right. An amount of 1 skips five coins and outputs 1. An amount of 99 gives 50, 20, 20, 5, 2, 2: six coins, the minimum.

Testing with a different coin set exposes a limit. With coins of 25, 10 and 1, the same steps give 30 as 25 + 1 + 1 + 1 + 1 + 1 (six coins), but 10 + 10 + 10 uses only three. The algorithm is correct for the shop's coins but not for every coin system, and finding a limit of this kind is what a "test and validate" part asks for.

Writing an algorithm in numbered steps

A numbered-steps answer must be precise enough that someone else could follow it without guessing. Examiners credit steps that say exactly what is compared, what changes and when the process stops. The comparison shows the difference between a vague answer and a creditable one for the change-giving problem.

Follow these rules when you write steps:

• One action per step, numbered, in the order they happen.

• Name the values you keep track of ("the amount", "the coin", "the count") and use the same name every time, so each step clearly refers to the same thing.

• Give every decision a precise condition, including whether a boundary counts: "greater than 0", "less than or equal to the amount".

• Make loops explicit: "repeat steps 3 to 5 while…" or "for each ticket in the pile…", and make sure the loop can end.

• Say what is output or returned, and when the algorithm stops.

• Don't hide the task inside one word. If the question is about sorting, "sort the cards" is not an algorithm; the steps must show the comparisons and moves.

Flowcharts

A flowchart shows an algorithm as standard symbols joined by arrows. You need to recognise each symbol, follow a flowchart exactly, and be able to draw a simple one.

The flowchart for the change-giving algorithm uses all six symbols. The loop is drawn as a flowline that returns to an earlier decision, and the connector A carries the flow from the "next smaller coin" box back to the main loop.

When you draw a flowchart yourself, put one action in each box, label both exits of every decision (Yes and No, or True and False), make each loop return to the decision that controls it, and use the right shape: a calculation in a parallelogram or an output in a rectangle loses the mark for that symbol.

Trace tables

To trace a flowchart is to follow it symbol by symbol and record every change in a trace table (tracing is taught in subtopic B1.1). The conventions are the same as for tracing code:

• one column for each variable, in the order the variables first appear;

• a column for each decision, if the question gives one, recording True/False or Yes/No;

• a column for output, written exactly as it is produced;

• a new row each time a value changes or a decision is made, so the order of events can be read from top to bottom.

If the question gives you a table with headings, use those headings and fill every row. If it gives a blank space, draw your own table with clear headings; a table is always clearer than a list of values in a sentence.

The commonest tracing slips are the same on paper as in code: updating a value at the wrong moment (subtracting the coin before the decision that checks it), stopping one pass early or late, and recording an output the flowchart never produces. A careful tracer moves a finger along the flowlines and writes a row at each decision.

Reasoning about efficiency without code

Some parts ask which of two methods is more efficient, or ask you to suggest a faster one and justify it. Without code, measure efficiency by counting the basic steps (comparisons, additions, moves) a method needs for an input of size $n$, and work out how that count grows as $n$ grows. The full theory is Big O notation in subtopic B2.4; for this question three ideas are usually enough.

• One pass through the data costs about $n$ steps: checking each ticket once, adding up every value, a linear search. The count grows in proportion to $n$.

• Comparing every item with every other item, or a full pass for each item, costs about $n\times n$ steps, so doubling $n$ makes the work four times as large.

• Halving the data at each step, as in a binary search of sorted data, costs about ${\log }_{2}n$ steps: 1,000 items need about 10 halvings.

State the worst case (the input that makes the method do the most work) unless the question asks for the best case, and say what causes it ("the missing ticket is the last number checked"). A good justification uses numbers: "for 1,000 tickets, at most 999,000 comparisons against 999 additions". The growth of the two kinds of cost for the raffle-ticket problem in worked example 2 shows why the difference matters for large inputs.

Time is not the only cost. A faster method sometimes uses more memory, such as an extra list of n tick boxes, and a good "evaluate" answer names that trade-off.

Worked example 1: tracing a flowchart

A weather station records the rainfall, in whole millimetres, for each of n days. The flowchart finds a value from the readings.

Part (e) is a typical "modify the algorithm" part: each change is one mark, and a frequent loss is updating the new variable in the wrong place (after day = day + 1, which records the next day instead). When you revise, you can check a hand trace by coding the same algorithm; the Python version returns 3, 0 and 4 for the readings in (b), in (c) and for four dry days in a row.

def longest_dry_spell(rain):
    current = 0
    longest = 0
    for amount in rain:
        if amount == 0:
            current = current + 1
            if current > longest:
                longest = current
        else:
            current = 0
    return longest


print(longest_dry_spell([0, 0, 3, 0, 0, 0, 1, 0]))
print(longest_dry_spell([2, 5, 1]))
print(longest_dry_spell([0, 0, 0, 0]))

public class DrySpell {
    public static int longestDrySpell(int[] rain) {
        int current = 0;
        int longest = 0;
        for (int amount : rain) {
            if (amount == 0) {
                current = current + 1;
                if (current > longest) {
                    longest = current;
                }
            } else {
                current = 0;
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        System.out.println(longestDrySpell(new int[] {0, 0, 3, 0, 0, 0, 1, 0}));
        System.out.println(longestDrySpell(new int[] {2, 5, 1}));
        System.out.println(longestDrySpell(new int[] {0, 0, 0, 0}));
    }
}

Worked example 2: designing and improving an algorithm

The second example has no flowchart: you build the algorithm yourself, then judge its efficiency. It follows the four-step process from exploring small cases to testing a better method.

A raffle uses tickets numbered 1 to n. After the draw, the box should contain every ticket, but exactly one is missing. The tickets in the box are in no particular order.

Testing Method B, as step 4 of the process demands, means trying the awkward cases. If ticket 1 is missing (tickets 2 to 6, total 20), it gives 21 − 20 = 1; if ticket n is missing, it gives n. Passing these tests shows only that the method works for the cases tried. Here a logical argument completes the job: the full total minus the total of the tickets present can only equal the number of the absent ticket, so the method is correct for every n.

Checklist

• To do:

  I know that one compulsory Paper 2 question has no code, and that it is also on the HL paper.

• To do:

  I can apply the four steps: explore small cases, record the steps, generalise, test and validate.

• To do:

  I test an algorithm with zero, one item, boundary values and a case that breaks the pattern.

• To do:

  I can write an algorithm as numbered steps, one action per step, with precise conditions and an explicit loop and stop.

• To do:

  I can name and draw the six flowchart symbols and label both exits of every decision.

• To do:

  I can trace a flowchart with a trace table, one row per decision or change, and state its output.

• To do:

  I can describe in words what a flowchart calculates.

• To do:

  I can modify an algorithm by adding a variable, its initial value, its update and its output.

• To do:

  I can compare two methods by counting steps for n items in the worst case.

• To do:

  I can suggest a more efficient method and justify it with numbers and a time–space trade-off.