← AS/A Level

CS · Chapter 12

Cambridge AS & A Level · Part 2 · Chapter 12

Algorithm Design and Problem-Solving

How to turn a problem into steps a computer can follow: abstraction, decomposition, pseudocode, flowcharts, loops and modules. Every worked example on this page runs in the step-through pseudocode lab.

Guru Jazzy
Chapter 12 opener: algorithm design and problem-solving

🎯 Learning objectives

By the end of this chapter you should be able to:

  • show an understanding of abstraction and describe its purpose
  • produce an abstract model of a system by including only the essential details
  • Describe and use decomposition
  • break problems down into sub-problems, leading to the idea of a program module
  • show that an algorithm is a solution expressed as a sequence of defined steps
  • choose suitable identifier names and record them in an identifier table
  • write pseudocode containing input, process and output
  • write pseudocode using the four basic constructs: assignment, sequence, selection and repetition
  • document a simple algorithm using pseudocode
  • write pseudocode from a structured English description or a flowchart
  • use stepwise refinement until a task is detailed enough to program
  • use logic statements to define parts of an algorithm

🧠 12.01 What is computational thinking?

Computational thinking is a problem-solving process: you take a number of logical steps to analyse a problem and reach a solution that people can understand and computers can carry out. It has five strands:

Abstraction: filtering out the information you don't need to solve the problem.
Decomposition: breaking a problem into sub-problems. This leads to program modules: procedures and functions.
Data modelling: analysing and organising data, e.g. abstract data types such as queues and stacks (Chapter 13), classes (Chapter 27), facts and rules (Chapter 29), random files (Chapter 26).
Pattern recognition: spotting common problems that already have standard solutions, such as sorting (13.03, 23.03) and searching (13.02, 23.04).
Algorithm design: developing step-by-step instructions to solve the problem.
Algorithm (key term): a sequence of defined steps that can be carried out to perform a task.

Abstraction in everyday life

The London Underground map (Figure 12.02) is a famous abstraction. It doesn't show where the tracks really run, or the streets above. It shows only the stations and which lines connect them, because that is all you need to plan a journey. Everything else has been filtered out.

Abstraction is what lets us cope with complexity. An algorithm is itself an abstraction of a process (inputs → steps → outputs), and an abstract data type defines a set of values and the operations on them, without saying how they are stored.

Task 12.01 Use the aerial photograph in Figure 12.01 and draw a map showing only the essential details for finding a route from landmark A to landmark B.
Figure 12.01Aerial photograph of part of a city, with landmarks A and B
What a good answer includes
  • Keep: A and B, the roads and footpaths you could walk along, the bridges over the canal, the railway line (as a barrier, and as a landmark), and junctions where you turn.
  • Leave out: trees, cars, roof colours, the exact shapes of buildings, the sports pitch and solar panels.
  • Straight lines and simple shapes are fine. Accurate distances and angles don't matter; which paths connect to which does.
  • Test it: could a friend who has never been there follow your map from A to B?

📋 12.02 What is an algorithm?

We follow algorithms every day. Changing a car wheel, from a manual:

  1. Take a spanner and loosen the wheel nuts.
  2. Position a jack in an appropriate place.
  3. Raise the car.
  4. Take off the wheel nuts and the wheel.
  5. Lift the replacement wheel into position.
  6. Replace the wheel nuts and tighten by hand.
  7. Lower the car.
  8. Fully tighten the wheel nuts.

The order matters. Do Step 1 after Step 3 and the wheel just spins in the air, so you can't loosen the nuts. You can't do Step 4 before Step 3 either.

🎮 Put the wheel-change steps in order

Use ▲ ▼ to move the steps, then check.

    A recipe is an algorithm

    1. Measure 200 g sugar, 200 g butter, 4 eggs, 200 g flour, 2 teaspoons baking powder and 2 tablespoons of milk.
    2. Mix the ingredients together in a large bowl until the mixture is smooth.
    3. Pour the mixture into a cake tin.
    4. Bake in the oven at 190 °C for 20 minutes.
    5. Check it is fully cooked.
    6. Turn the cake out of the tin and cool on a wire rack.

    The ingredients are the input, the cake is the output, and mixing and baking is the process.

    Some steps need breaking down further. Step 2 becomes:

    1. 2.1 Beat the sugar and butter together until fluffy.
    2. 2.2 Add the eggs, one at a time, mixing constantly.
    3. 2.3 Sieve the flour and baking powder and stir slowly into the egg mixture.
    4. 2.4 Add milk and mix to give a creamy consistency.

    🚇 Steps that depend on a condition

    Figure 12.02Part of the London Underground map, showing the Piccadilly, Victoria and Jubilee lines

    From King's Cross St. Pancras to Westminster there are two routes:

    • Route A: Victoria line to Green Park (4 stations), then Jubilee line to Westminster (1 station).
    • Route B: Piccadilly line to Green Park (6 stations), then Jubilee line to Westminster (1 station).

    Route A looks best, but if there are engineering works on the Victoria line, Route B might be quicker. So the directions contain a choice:

    IF there are engineering works on the Victoria Line
    THEN
        Take the Piccadilly Line to Green Park (6 stations)
        Take the Jubilee Line to Westminster (1 station)
    ELSE
        Take the Victoria Line to Green Park (4 stations)
        Take the Jubilee Line to Westminster (1 station)
ENDIF

    🔬 Lab: follow the IF

    Task 12.02 Write the steps to be followed to: make a sandwich · walk from your school or college to the nearest shop · log on to your computer.
    Example answer: log on to your computer
    1. Press the power button and wait for the log-on screen.
    2. Click on your user name (or type it in).
    3. Type your password.
    4. Press Enter.
    5. IF the password is rejected THEN go back to Step 3 (after 3 failures, ask your teacher) ELSE wait for the desktop to appear.

    Check your own answers: is every step one clear action? Is the order forced (could step 4 come before step 3)? Did you need a condition (IF) or a repeat?

    Many problems have more than one solution. Sometimes the choice is a personal preference; sometimes one solution is measurably better.

    ✍️ 12.03 Expressing algorithms

    Tip: Computer scientists want good solutions: correct results, as little memory as possible, as fast as possible, and concise, elegant and easy to understand.

    We write a solution (an algorithm) as a sequence of steps in structured English or pseudocode, or draw it as a flowchart.

    Structured English: a subset of the English language that consists of command statements used to describe an algorithm.
    Pseudocode: a way of using keywords and identifiers to describe an algorithm without following the syntax of a particular programming language.
    Flowchart: shapes linked together to represent the sequential steps of an algorithm.

    The four basic constructs

    Assignment: a value is given a name (identifier), or the value linked to an identifier is changed.
    Sequence: steps are performed one after the other.
    Selection: under certain conditions some steps are performed, otherwise different (or no) steps are.
    Repetition: a sequence of steps is performed a number of times. Also called iteration or looping.

    Most problems involve data: we input it, process it and output results (Figure 12.03), so we also need input and output statements.

    Figure 12.03Input → process → output

    Knowing the constructs tells you how detailed your design must be. Table 12.01 shows each one in all three notations.

    ConstructStructured EnglishPseudocode
    Assignment & sequenceSET A TO 34
    INCREMENT B    		A ← 34
    B ← B + 1
    SelectionIF A IS GREATER THAN B
      THEN …
      ELSE …    		IF A > B
      THEN …
      ELSE …
    ENDIF
    RepetitionREPEAT UNTIL A IS EQUAL TO B …REPEAT
      …
    UNTIL A = B
    InputINPUT AINPUT "Prompt: " A
    OutputOUTPUT "Message"
    OUTPUT B    		OUTPUT "Message", B
    Table 12.01Constructs for computing algorithms in structured English, pseudocode and flowcharts: assignment and sequence, selection, repetition, input
    Table 12.01 (cont.)Constructs for computing algorithms (continued): output
    Flowchart shapes: rounded box = Start/End · rectangle = a process (assignment) · diamond = a decision with Yes/No exits · parallelogram = input or output · a box with double side bars = a procedure call (Figure 12.11).

    🎮 Which construct is it?

    📦 12.04 Variables

    When data is input, each value is stored in memory. To write statements about it, we need to name that memory location. A named memory location is a variable: think of a box with a name label on it.

    Variable: a storage location for a data value that has an identifier.

    In a number-guessing game, the count of guesses might be stored in NumberOfGuesses and the player's name in ThisPlayer.

    Figure 12.04Variables as labelled boxes: NumberOfGuesses holds 5, ThisPlayer holds "Fred"
    • Identifiers contain no spaces: only letters, digits and _ (underscore).
    • The name should say what the variable is used for, so it is often several words joined together.
    • The convention used in the book is CamelCaps: NumberOfGuesses, ThisPlayer. It makes long identifiers easy to read.

    🎮 Valid identifier?

    ➡️ 12.05 Assignments

    Assigning a value

    INPUT Number stores the value that is typed in (say 15) in the variable Number. NumberOfGuesses ← 1 stores the value 1 in NumberOfGuesses.

    Figure 12.05Variables being assigned a value: (a) INPUT Number stores 15, (b) NumberOfGuesses ← 1

    Updating a value

    NumberOfGuesses ← NumberOfGuesses + 1 takes the value stored in NumberOfGuesses, adds 1, and stores the new value back in the same variable. Read ← as "becomes".

    Figure 12.06Updating the value of a variable: NumberOfGuesses goes from 1 to 2

    Copying a value

    Value2 ← Value1 copies the value from Value1 into Value2. Value1 keeps its value until something else is assigned to it.

    Figure 12.07Copying the value of a variable: Value2 ← Value1

    Swapping two values

    To swap the contents of two variables, you must park one value in a temporary variable first. Otherwise the second value to be moved is overwritten by the first.

    Figure 12.08Swapping the values of two variables using Temp, in three steps (a), (b), (c)
    Temp ← Value1
Value1 ← Value2
Value2 ← Temp

    (a) copy Value1 into Temp; (b) copy Value2 into Value1; (c) copy Temp into Value2.

    🔬 Lab: swap the boxes

    Goal: finish with Value1 = 34 and Value2 = 15. Each button is one assignment. Try it first without Temp and see what happens.

    Worked Example 12.01

    Using input, output, assignment and sequence constructs

    Problem: convert a distance in miles and output the equivalent distance in km.

    Step 1: write the problem as structured English statements:

    INPUT number of miles
Calculate number of km
OUTPUT calculated result as km

    Step 2: analyse the data values needed. We need one variable for the distance in miles and one for the result of multiplying the miles by 1.61. List them in an identifier table:

    IdentifierExplanation
    MilesDistance as a whole number of miles
    KmThe result from using the given formula: Km = Miles * 1.61

    Table 12.02 Identifier table for miles to km conversion

    Step 3: add detail with a flowchart or pseudocode. Both should show the same level of detail, using only the constructs in Table 12.01.

    Figure 12.09Flowchart for miles to km conversion
    INPUT "Enter miles:" Miles
Km ← Miles * 1.61
OUTPUT "km: ", Km
    Identifier table: a table listing the variable identifiers required for the solution, with explanations and data types (see Chapter 13).
    Task 12.03 Consider these algorithm steps: 1 Input a length in inches. 2 Calculate the equivalent in centimetres. 3 Output the result. List the variables required in an identifier table, then write pseudocode for the algorithm.
    Model answer
    IdentifierExplanation
    InchesThe length input, in inches
    CentimetresThe result: Centimetres = Inches * 2.54
    INPUT "Enter a length in inches: " Inches
Centimetres ← Inches * 2.54
OUTPUT "Centimetres: ", Centimetres

    🔀 12.06 Logic statements

    The Underground directions in 12.02 followed one set of steps or another depending on a condition. The selection construct does exactly this (Figure 12.10):

    IF A < B          // ← a simple condition
    THEN
        <statement(s)>
    ELSE
        <statement(s)>
ENDIF

    Figure 12.10 Pseudocode for the selection construct

    A condition contains at least one logic proposition (Chapter 4, Section 4.01). Propositions use the relational (comparison) operators:

    OperatorComparison
    =Is equal to
    <Is less than
    >Is greater than
    <=Is less than or equal to
    >=Is greater than or equal to
    <>Is not equal to

    Table 12.03 Relational operators

    Conditions are either TRUE or FALSE. In pseudocode, = tests for equality, while ← assigns a value. Don't mix them up.

    A person is a child if they are under 13 and an adult if they are over 19. Between 13 and 19 inclusive, they are a teenager:

    • If Age < 13 then person is a child.
    • If Age > 19 then person is an adult.
    • If Age >= 13 AND Age <= 19 then person is a teenager.

    🔬 Lab: evaluate the conditions

    Task 12.04 A town has a bus service where passengers under the age of 12 and over the age of 60 do not need to pay a fare. Write the logic statements for free fares.

    🎮 Pick the condition for a free fare

    Careful: the English says "under 12 and over 60", but no one can be both. Test each condition on these passengers.

    AgeShould be free?Your condition says
    Model answer

    If Age < 12 OR Age > 60 then fare is free. (Equivalently: If NOT (Age >= 12 AND Age <= 60) then fare is free.) Otherwise the passenger pays: If Age >= 12 AND Age <= 60 then fare is paid.

    🎲 The number-guessing game

    • The player inputs a number to guess the secret number stored.
    • If the guess was correct, output a congratulations message.
    • If the number input was larger than the secret number, output "secret number is smaller".
    • If the number input was smaller than the secret number, output "secret number is greater".
    SecretNumber ← Random   // a whole number from 1 to 100
INPUT Guess
IF Guess = SecretNumber
    THEN
        OUTPUT "Well done. You have guessed the secret number"
    ELSE
        IF Guess > SecretNumber
            THEN
                OUTPUT "secret number is smaller"
            ELSE
                OUTPUT "secret number is greater"
        ENDIF
ENDIF

    More complex conditions use the logical operators AND, OR and NOT. Suppose the player has several guesses, and after 10 wrong guesses a different message appears:

    IF Guess = SecretNumber
    THEN
        OUTPUT "Well done. You have guessed the secret number"
    ELSE
        IF Guess <> SecretNumber AND NumberOfGuesses = 10   // complex condition
            THEN
                OUTPUT "You still have not guessed the secret number"
            ELSE
                IF Guess > SecretNumber
                    THEN
                        OUTPUT "secret number is smaller"
                    ELSE
                        OUTPUT "secret number is greater"
                ENDIF
        ENDIF
ENDIF
    Note: the book spells one identifier NumberofGuesses here; it should be NumberOfGuesses everywhere. Also, inside that ELSE we already know Guess <> SecretNumber, so NumberOfGuesses = 10 on its own would do.
    Worked Example 12.02

    Using selection constructs

    Problem: take three numbers as input and output the largest number. One method:

    1. Input all three numbers at the beginning.
    2. Store each input value in a separate variable (Table 12.04).
    3. Compare the first number with the second, then compare the bigger of these with the third.
    4. Output the bigger number from this second comparison.
    IdentifierExplanation
    Number1The first number to be input
    Number2The second number to be input
    Number3The third number to be input

    Table 12.04 Identifier table for biggest number problem

    INPUT Number1
INPUT Number2
INPUT Number3
IF Number1 > Number2
    THEN
        // Number1 is bigger
        IF Number1 > Number3
            THEN
                OUTPUT Number1
            ELSE
                OUTPUT Number3
        ENDIF
    ELSE
        // Number2 is bigger
        IF Number2 > Number3
            THEN
                OUTPUT Number2
            ELSE
                OUTPUT Number3
        ENDIF
ENDIF

    When an IF statement contains another IF statement, they are nested IF statements.

    Nested IF statements: conditional statements within conditional statements.
    Question 12.01 What changes do you need to make to output the smallest number?
    Answer

    Change every > to <: IF Number1 < Number2, IF Number1 < Number3, IF Number2 < Number3. Update the comments to "is smaller" too. The structure stays the same.

    Worked Example 12.03

    Using selection constructs (alternative method)

    Same problem, different algorithm:

    1. Input the first number and store it in BiggestSoFar.
    2. Input the second number and compare it with BiggestSoFar.
    3. If the second number is bigger, assign its value to BiggestSoFar.
    4. Input the third number and compare it with BiggestSoFar.
    5. If the third number is bigger, assign its value to BiggestSoFar.
    6. Output the value stored in BiggestSoFar.
    IdentifierExplanation
    BiggestSoFarStores the biggest number input so far
    NextNumberThe next number to be input

    Table 12.05 Identifier table for the alternative solution

    INPUT BiggestSoFar
INPUT NextNumber
IF NextNumber > BiggestSoFar
    THEN
        BiggestSoFar ← NextNumber
ENDIF
INPUT NextNumber
IF NextNumber > BiggestSoFar
    THEN
        BiggestSoFar ← NextNumber
ENDIF
OUTPUT BiggestSoFar

    When the third number is input, the second is overwritten because it is no longer needed.

    Advantages of 12.03 over 12.02:
    • Only two variables are used.
    • The IFs are not nested and have no ELSE, so they are easier to understand.
    • It adapts easily to more numbers (Worked Example 12.04).
    Disadvantage: more work for the computer. If the second number is bigger than the first, BiggestSoFar changes; if the third is bigger again, it changes again. Depending on the inputs, that's up to two extra assignments.

    🔁 12.07 Loops

    In Worked Example 12.03 the two IF statements are identical. Comparing 10 numbers would need that IF nine times; 100 numbers would be very tedious. A repetition construct (a loop) avoids writing the same lines over and over.

    Worked Example 12.04

    Repetition using REPEAT…UNTIL

    Problem: take 10 numbers as input and output the largest number. We need one more variable: a counter, so we know when we have compared 10 numbers.

    IdentifierExplanation
    BiggestSoFarStores the biggest number input so far
    NextNumberThe next number to be input
    CounterStores how many numbers have been input so far

    Table 12.06 Identifier table using REPEAT…UNTIL

    INPUT BiggestSoFar
Counter ← 1
REPEAT
    INPUT NextNumber
    Counter ← Counter + 1
    IF NextNumber > BiggestSoFar
        THEN
            BiggestSoFar ← NextNumber
    ENDIF
UNTIL Counter = 10
OUTPUT BiggestSoFar

    Each new number overwrites the previous one, which is no longer needed.

    Question 12.02 What changes do you need to make to the algorithm in Worked Example 12.04: (a) to compare 100 numbers? (b) to take as a first input the number of numbers to be compared?
    Answer

    (a) Change UNTIL Counter = 10 to UNTIL Counter = 100.

    (b) Add INPUT HowMany as the very first line (add it to the identifier table) and change the last test to UNTIL Counter = HowMany. Note that REPEAT always runs at least once, so this still assumes HowMany is at least 2.

    Another loop does the counting for us: FOR…NEXT.

    Worked Example 12.05

    Repetition using FOR…NEXT

    Same problem and identifiers, but now Counter counts the number of times round the loop.

    Table 12.07: BiggestSoFar · NextNumber · Counter (counts the number of times round the loop)

    INPUT BiggestSoFar
FOR Counter ← 2 TO 10
    INPUT NextNumber
    IF NextNumber > BiggestSoFar
        THEN
            BiggestSoFar ← NextNumber
    ENDIF
NEXT Counter
OUTPUT BiggestSoFar

    First time round, Counter is 2. Next time it has automatically increased to 3, and so on; the last time round it is 10.

    Rogue value: a value used to terminate a sequence of values. It is the same data type as the data but outside the range of normal expected values.
    Worked Example 12.06

    Repetition using a rogue value

    Problem: a sequence of non-zero numbers is terminated by 0. Take this sequence as input and output the largest number.

    The rogue value here is 0. Choose a rogue value of the same type but outside the normal range: if 0 could be real data, use something like −1. Instead of counting, the loop checks whether the input is 0.

    Table 12.08: BiggestSoFar · NextNumber

    INPUT BiggestSoFar
REPEAT
    INPUT NextNumber
    IF NextNumber > BiggestSoFar
        THEN
            BiggestSoFar ← NextNumber
    ENDIF
UNTIL NextNumber = 0
OUTPUT BiggestSoFar
    INPUT NextNumber
BiggestSoFar ← NextNumber
WHILE NextNumber <> 0 DO // sequence terminator not encountered
    INPUT NextNumber
    IF NextNumber > BiggestSoFar
        THEN
            BiggestSoFar ← NextNumber
    ENDIF
ENDWHILE
OUTPUT BiggestSoFar

    The REPEAT version works even for one non-zero input, but not when the only input is 0. Then we don't want the loop body to run at all, so we use WHILE…ENDWHILE. The first number goes into both NextNumber and BiggestSoFar; if it is zero, the loop body is skipped. For a non-zero first number, it does the same as REPEAT…UNTIL.

    Try it: in the lab, put just 0 in the inputs for each version. The REPEAT version waits for another number, because it always runs its body once.
    Worked Example 12.07

    Implementing the number-guessing game with a loop

    1. The player repeatedly inputs a number to guess the secret number stored.
    2. If the guess is correct, the number of guesses made is output and the game stops.
    3. If the number input is larger than the secret number, the player is told to input a smaller number.
    4. If the number input is smaller, the player is told to input a larger number.

    Structured English:

    SET value for secret number
REPEAT the following UNTIL correct guess
    INPUT guess
    count number of guesses
    COMPARE guess with secret number
    OUTPUT comment
OUTPUT number of guesses
    IdentifierExplanation
    SecretNumberThe number to be guessed
    NumberOfGuessesThe number of guesses the player has made
    GuessThe number the player has input as a guess

    Table 12.09 Identifier table for number-guessing game

    FlowchartFlowchart for the number-guessing game with repeated guesses

    Pseudocode with a post-condition loop:

    SecretNumber ← Random   // a whole number from 1 to 100
NumberOfGuesses ← 0
REPEAT
    INPUT Guess
    NumberOfGuesses ← NumberOfGuesses + 1
    IF Guess > SecretNumber
        THEN
            OUTPUT "Input a smaller number"
    ENDIF
    IF Guess < SecretNumber
        THEN
            OUTPUT "Input a larger number"
    ENDIF
UNTIL Guess = SecretNumber
OUTPUT NumberOfGuesses

    Pseudocode with a pre-condition loop (this is the one that matches the flowchart):

    SecretNumber ← Random   // a whole number from 1 to 100
INPUT Guess
NumberOfGuesses ← 1
WHILE Guess <> SecretNumber DO
    IF Guess > SecretNumber
        THEN
            OUTPUT "Input a smaller number"
    ENDIF
    IF Guess < SecretNumber
        THEN
            OUTPUT "Input a larger number"
    ENDIF
    INPUT Guess
    NumberOfGuesses ← NumberOfGuesses + 1
ENDWHILE
OUTPUT NumberOfGuesses
    Note: the book writes the messages as comments (// the player is given the message to input a smaller number). We've turned them into OUTPUT statements so the lab can show them. Notice NumberOfGuesses starts at 0 in the REPEAT version but at 1 in the WHILE version, because there the first guess is input before the loop.
    Worked Example 12.08

    Calculating running totals and averages

    Problem: take 10 numbers as input and output their sum and their average.

    IdentifierExplanation
    RunningTotalStores the sum of the numbers input so far
    CounterHow many numbers have been input
    NextNumberThe next number input
    AverageThe average of the numbers input

    Table 12.10 Identifier table for running total and average

    RunningTotal ← 0
FOR Counter ← 1 TO 10
    INPUT NextNumber
    RunningTotal ← RunningTotal + NextNumber
NEXT Counter
OUTPUT RunningTotal
Average ← RunningTotal / 10
OUTPUT Average

    It is very important to initialise RunningTotal to zero before adding the numbers.

    Tip: which type of loop? If you know how many repetitions you need, choose FOR. If the loop body might never need to run, choose WHILE. If the body must run at least once, REPEAT is more sensible.

    🎮 Which loop fits best?

    Task 12.05 Change the algorithm in Worked Example 12.08 so that the sequence of numbers is terminated by a rogue value of 0.
    Model answer

    We no longer know how many numbers there are, so the FOR loop becomes a WHILE loop and Counter has to be counted by hand. The average divides by Counter, and only when at least one number was input.

    RunningTotal ← 0
Counter ← 0
INPUT NextNumber
WHILE NextNumber <> 0 DO
    RunningTotal ← RunningTotal + NextNumber
    Counter ← Counter + 1
    INPUT NextNumber
ENDWHILE
OUTPUT RunningTotal
IF Counter > 0
    THEN
        Average ← RunningTotal / Counter
        OUTPUT Average
ENDIF
    Worked Example 12.09

    Using nested loops

    Problem: take as input two numbers and a symbol. Output a grid made entirely of the symbol, with the number of rows given by the first number and the number of columns by the second. Inputs 3, 7 and & give:

    &&&&&&&
&&&&&&&
&&&&&&&
    IdentifierExplanation
    NumberOfRowsStores the number of rows of the grid
    NumberOfColumnsStores the number of columns of the grid
    SymbolStores the chosen character symbol
    RowCounterCounts the number of rows
    ColumnCounterCounts the number of columns

    Table 12.11 Identifier table for the nested loop example

    INPUT NumberOfRows
INPUT NumberOfColumns
INPUT Symbol
FOR RowCounter ← 1 TO NumberOfRows
    FOR ColumnCounter ← 1 TO NumberOfColumns
        OUTPUT Symbol // without moving to next line
    NEXT ColumnCounter
    OUTPUT Newline   // move to the next line
NEXT RowCounter

    Each time round the outer loop (rows), the inner loop runs completely, outputting one symbol per column. This is a nested loop.

    Nested loop: a loop containing another loop.

    🪜 12.08 Stepwise refinement

    Bigger problems are easier if you break them into smaller steps, and break those down again until each step is easy. To be programmable, every step must end up as one of the basic constructs: sequence, assignment, selection, repetition, input or output.

    Stepwise refinement does this to an outline solution. The cake recipe in 12.02 was an example: "mix the ingredients" was refined into Steps 2.1 to 2.4.

    Stepwise refinement: breaking down the steps of an outline solution into smaller and smaller steps.
    Worked Example 12.10

    Drawing a pyramid using stepwise refinement

    Problem: take as input a chosen symbol and an odd number. Output a pyramid made entirely of the symbol, with the number of symbols in the final row equal to the number input. Inputs A and 9 give:

        A
   AAA
  AAAAA
 AAAAAAA
AAAAAAAAA

    It is like Worked Example 12.09, but the symbols per row start at 1 and go up by 2 each row, and each row starts with one fewer space to create the slope. First attempt, in structured English:

    01  Set up initial values
02  REPEAT
03      Output number of spaces
04      Output number of symbols
05      Adjust number of spaces and number of symbols to be output in next row
06  UNTIL the required number of symbols have been output in one row

    The steps are numbered so we can refer to them. This isn't detailed enough to program: exactly what values do we need?

    • Input: the symbol, and the number of symbols in the final row (odd, so the pyramid is symmetrical).
    • Spaces in the first row: half of (final row's symbols − 1). Symbols in the first row: 1.
    IdentifierExplanation
    SymbolThe character symbol to form the pyramid
    MaxNumberOfSymbolsThe number of symbols in the final row
    NumberOfSpacesThe number of spaces to be output in the current row
    NumberOfSymbolsThe number of symbols to be output in the current row

    Table 12.12 Identifier table for pyramid example

    Open each outline step to see how it is refined. The numbering shows which step is being refined.

    01   // Set up initial values expands into:
01.1 INPUT Symbol
01.2 INPUT MaxNumberOfSymbols
01.3 NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
01.4 NumberOfSymbols ← 1

    We need an odd number for MaxNumberOfSymbols, so Step 01.2 is refined again:

    01.2   // INPUT MaxNumberOfSymbols expands into:
01.2.1 REPEAT
01.2.2     INPUT MaxNumberOfSymbols
01.2.3 UNTIL MaxNumberOfSymbols MOD 2 = 1
01.2.4 // MOD 2 gives the remainder after integer division by 2
    03   // Output number of spaces expands into:
03.1 FOR i ← 1 TO NumberOfSpaces
03.2     OUTPUT Space // without moving to next line
03.3 NEXT i
    04   // Output number of symbols expands into:
04.1 FOR i ← 1 TO NumberOfSymbols
04.2     OUTPUT Symbol // without moving to next line
04.3 NEXT i
04.4 OUTPUT Newline // move to the next line

    Decrease the spaces by 1 and increase the symbols by 2:

    05   // Adjust values for next row expands into:
05.1 NumberOfSpaces ← NumberOfSpaces - 1
05.2 NumberOfSymbols ← NumberOfSymbols + 2

    Check whether the number of symbols for the next row is now greater than the value input at the beginning:

    06   UNTIL NumberOfSymbols > MaxNumberOfSymbols

    Putting all the steps together:

    01     // Set Values
01.1   INPUT Symbol
01.2   // Input max number of symbols (an odd number)
01.2.1 REPEAT
01.2.2     INPUT MaxNumberOfSymbols
01.2.3 UNTIL MaxNumberOfSymbols MOD 2 = 1
01.3   NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
01.4   NumberOfSymbols ← 1
02     REPEAT
03         // Output number of spaces
03.1       FOR i ← 1 TO NumberOfSpaces
03.2           OUTPUT Space // without moving to next line
03.3       NEXT i
04         // Output number of symbols
04.1       FOR i ← 1 TO NumberOfSymbols
04.2           OUTPUT Symbol // without moving to next line
04.3       NEXT i
04.4       OUTPUT Newline // move to the next line
05         // Adjust Values For Next Row
05.1       NumberOfSpaces ← NumberOfSpaces - 1
05.2       NumberOfSymbols ← NumberOfSymbols + 2
06     UNTIL NumberOfSymbols > MaxNumberOfSymbols

    🔬 Lab: pyramid and hollow triangle

    RowNumberOfSpacesNumberOfSymbols

    Spaces are shown as faint dots so you can count them.

    Task 12.06 Use stepwise refinement to output a hollow triangle. Inputs A and 9 give: 
        A
   A A
  A   A
 A     A
AAAAAAAAA
    A first attempt in structured English: 
    01  Set up initial values
02  REPEAT
03      Output leading number of spaces
04      Output symbol, middle spaces, symbol
05      Adjust number of spaces and number of symbols to be output in next row
06  UNTIL the required number of symbols have been output in one row
    Model answer

    Keep track of MiddleSpaces as well as the leading spaces. Top row: one symbol only. Bottom row (no leading spaces): a full row of symbols. Every other row: symbol, MiddleSpaces spaces, symbol, with MiddleSpaces going −1, 1, 3, 5, …

    01     // Set up initial values
01.1   INPUT Symbol
01.2.1 REPEAT
01.2.2     INPUT MaxNumberOfSymbols
01.2.3 UNTIL MaxNumberOfSymbols MOD 2 = 1
01.3   NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
01.4   MiddleSpaces ← -1  // the top row has no middle
02     REPEAT
03         // Output leading number of spaces
03.1       FOR i ← 1 TO NumberOfSpaces
03.2           OUTPUT Space // without moving to next line
03.3       NEXT i
04         // Output symbol, middle spaces, symbol
04.1       IF NumberOfSpaces = 0
04.2           THEN  // bottom row: a full line of symbols
04.3               FOR i ← 1 TO MaxNumberOfSymbols
04.4                   OUTPUT Symbol // without moving to next line
04.5               NEXT i
04.6           ELSE
04.7               OUTPUT Symbol // without moving to next line
04.8               IF MiddleSpaces > 0
04.9                   THEN
04.10                      FOR i ← 1 TO MiddleSpaces
04.11                          OUTPUT Space // without moving to next line
04.12                      NEXT i
04.13                      OUTPUT Symbol // without moving to next line
04.14              ENDIF
04.15      ENDIF
04.16      OUTPUT Newline // move to the next line
05         // Adjust values for next row
05.1       NumberOfSpaces ← NumberOfSpaces - 1
05.2       MiddleSpaces ← MiddleSpaces + 2
06     UNTIL NumberOfSpaces < 0

    🧩 12.09 Modules

    Another way to develop a solution is to decompose the problem into sub-tasks. Each sub-task is a module that is refined separately. Modules are procedures and functions.

    A procedure groups some steps and gives them a name (identifier). To perform those steps, we call the procedure by its name.

    Procedure: a sequence of steps that is given an identifier and can be called to perform a sub-task.
    Figure 12.11Representation of a procedure in (a) pseudocode and (b) a flowchart

    A function also groups steps under a name, but they produce and return a value that is used in an expression.

    Function: a sequence of steps that is given an identifier and returns a single value; a function call is part of an expression.

    Because a function returns a value, its definition states that value's data type (Chapter 13). Module identifiers follow the same rules as variable identifiers (12.04).

    Worked Example 12.11

    Drawing a pyramid using modules

    Same problem as Worked Example 12.10. To set up the initial values we call a procedure: CALL SetValues. The top level uses one procedure per step, so each procedure has to be defined:

    CALL SetValues
REPEAT
    CALL OutputSpaces
    CALL OutputSymbols
    CALL AdjustValuesForNextRow
UNTIL NumberOfSymbols > MaxNumberOfSymbols

PROCEDURE SetValues
    INPUT Symbol
    CALL InputMaxNumberOfSymbols // need to ensure it is an odd number
    NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
    NumberOfSymbols ← 1
ENDPROCEDURE

PROCEDURE InputMaxNumberOfSymbols
    REPEAT
        INPUT MaxNumberOfSymbols
    UNTIL MaxNumberOfSymbols MOD 2 = 1
ENDPROCEDURE

PROCEDURE OutputSpaces
    FOR Count1 ← 1 TO NumberOfSpaces
        OUTPUT Space // without moving to next line
    NEXT Count1
ENDPROCEDURE

PROCEDURE OutputSymbols
    FOR Count2 ← 1 TO NumberOfSymbols
        OUTPUT Symbol // without moving to next line
    NEXT Count2
    OUTPUT Newline // move to the next line
ENDPROCEDURE

PROCEDURE AdjustValuesForNextRow
    NumberOfSpaces ← NumberOfSpaces - 1
    NumberOfSymbols ← NumberOfSymbols + 2
ENDPROCEDURE
    Task 12.07 Amend your algorithm for Task 12.05 to use modules.
    Model answer

    One procedure per job: set up, add one number, output the results. (If your teacher meant Task 12.06, use the same idea: SetValues, OutputLeadingSpaces, OutputRow, AdjustValues.)

    CALL Initialise
INPUT NextNumber
WHILE NextNumber <> 0 DO
    CALL AddToTotal
    INPUT NextNumber
ENDWHILE
CALL OutputResults

PROCEDURE Initialise
    RunningTotal ← 0
    Counter ← 0
ENDPROCEDURE

PROCEDURE AddToTotal
    RunningTotal ← RunningTotal + NextNumber
    Counter ← Counter + 1
ENDPROCEDURE

PROCEDURE OutputResults
    OUTPUT RunningTotal
    IF Counter > 0
        THEN
            OUTPUT RunningTotal / Counter
    ENDIF
ENDPROCEDURE
    Worked Example 12.12

    Drawing a pyramid using procedures and functions

    Same problem again. The top level now calls three procedures and uses two functions, in lines 05.1 and 05.2. Procedure SetValues also uses a function, ValidatedMaxNumberOfSymbols.

    01   CALL SetValues
02   REPEAT
03       CALL OutputSpaces
04       CALL OutputSymbols
05.1     NumberOfSpaces ← AdjustedNumberOfSpaces
05.2     NumberOfSymbols ← AdjustedNumberOfSymbols
06   UNTIL NumberOfSymbols > MaxNumberOfSymbols

PROCEDURE SetValues
    INPUT Symbol
    MaxNumberOfSymbols ← ValidatedMaxNumberOfSymbols
    NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
    NumberOfSymbols ← 1
ENDPROCEDURE

FUNCTION ValidatedMaxNumberOfSymbols RETURNS INTEGER
    REPEAT
        INPUT MaxNumberOfSymbols
    UNTIL MaxNumberOfSymbols MOD 2 = 1
    RETURN MaxNumberOfSymbols
ENDFUNCTION

PROCEDURE OutputSpaces
    FOR Count1 ← 1 TO NumberOfSpaces
        OUTPUT Space // without moving to next line
    NEXT Count1
ENDPROCEDURE

PROCEDURE OutputSymbols
    FOR Count2 ← 1 TO NumberOfSymbols
        OUTPUT Symbol // without moving to next line
    NEXT Count2
    OUTPUT Newline // move to the next line
ENDPROCEDURE

FUNCTION AdjustedNumberOfSpaces RETURNS INTEGER
    NumberOfSpaces ← NumberOfSpaces - 1
    RETURN NumberOfSpaces
ENDFUNCTION

FUNCTION AdjustedNumberOfSymbols RETURNS INTEGER
    NumberOfSymbols ← NumberOfSymbols + 2
    RETURN NumberOfSymbols
ENDFUNCTION
    Book typo fixed: line 05.2 in the book calls AdjustedNumbeOfSymbols (missing "r"), but the function is defined as AdjustedNumberOfSymbols. A real program would stop with "unknown identifier".

    A benefit of modules is that they can be reused in other solutions. So modules should be self-contained: they shouldn't rely on outside variables. Everything a module needs should be passed to it as parameters.

    Worked Example 12.13

    Drawing a pyramid using modules and parameters

    Same problem as Worked Example 12.12, but every value a module needs is passed in as a parameter.

    01   CALL SetValues(Symbol, MaxNumberOfSymbols, NumberOfSpaces, NumberOfSymbols)
02   REPEAT
03       CALL OutputSpaces(NumberOfSpaces)
04       CALL OutputSymbols(NumberOfSymbols, Symbol)
05.1     NumberOfSpaces ← AdjustedNumberOfSpaces(NumberOfSpaces)
05.2     NumberOfSymbols ← AdjustedNumberOfSymbols(NumberOfSymbols)
06   UNTIL NumberOfSymbols > MaxNumberOfSymbols

PROCEDURE SetValues(BYREF Symbol : CHAR, MaxNumberOfSymbols : INTEGER, NumberOfSpaces : INTEGER, NumberOfSymbols : INTEGER)
    INPUT Symbol
    MaxNumberOfSymbols ← ValidatedMaxNumberOfSymbols
    NumberOfSpaces ← (MaxNumberOfSymbols - 1) / 2
    NumberOfSymbols ← 1
ENDPROCEDURE

FUNCTION ValidatedMaxNumberOfSymbols RETURNS INTEGER
    DECLARE MaxSymbols : INTEGER
    REPEAT
        INPUT MaxSymbols
    UNTIL MaxSymbols MOD 2 = 1
    RETURN MaxSymbols
ENDFUNCTION

PROCEDURE OutputSpaces(NumberOfSpaces : INTEGER)
    DECLARE Count1 : INTEGER
    FOR Count1 ← 1 TO NumberOfSpaces
        OUTPUT Space // without moving to next line
    NEXT Count1
ENDPROCEDURE

PROCEDURE OutputSymbols(NumberOfSymbols : INTEGER, Symbol : CHAR)
    DECLARE Count2 : INTEGER
    FOR Count2 ← 1 TO NumberOfSymbols
        OUTPUT Symbol // without moving to next line
    NEXT Count2
    OUTPUT Newline // move to the next line
ENDPROCEDURE

FUNCTION AdjustedNumberOfSpaces(NumberOfSpaces : INTEGER) RETURNS INTEGER
    NumberOfSpaces ← NumberOfSpaces - 1
    RETURN NumberOfSpaces
ENDFUNCTION

FUNCTION AdjustedNumberOfSymbols(NumberOfSymbols : INTEGER) RETURNS INTEGER
    NumberOfSymbols ← NumberOfSymbols + 2
    RETURN NumberOfSymbols
ENDFUNCTION
    Two corrections to the book's version. (1) SetValues must send its four values back to the caller, so its parameters have to be passed BYREF (by reference, Chapter 14). In the book they look like ordinary (BYVAL) parameters, and the main program would never receive the values. In Cambridge pseudocode, BYREF applies to every parameter after it. (2) The book again spells it AdjustedNumbeOfSymbols; fixed here. We also added DECLARE lines so Count1, Count2 and MaxSymbols are really local. Watch them appear under Local in the lab.

    Procedure OutputSpaces uses Count1 only inside the module, and OutputSymbols uses Count2 only inside the module. Such a variable is a local variable (Chapter 14, Section 14.09). A variable available to all modules is a global variable.

    Tip: Good design uses local variables, because they make modules independent and reusable.
    Local variable: a variable that is accessible only within the module in which it is declared.
    Global variable: a variable that is accessible from all modules.
    Reflection point: Can you think of other problems and use decomposition to break them down into basic constructs, input and output statements?

    🧪 Pseudocode lab

    Pick a program, then press Step to run it one line at a time. The highlighted line is about to run. Watch the variables change and the output appear. Inputs are taken from the box on the right, left to right; if it runs out, the program asks you. Press Edit to change the code or write your own (Cambridge 9618 style: ← or <-, IF/THEN/ELSE/ENDIF, REPEAT/UNTIL, WHILE/DO/ENDWHILE, FOR/TO/NEXT, PROCEDURE, FUNCTION/RETURNS/RETURN, CALL, BYREF, DECLARE, MOD, DIV, AND/OR/NOT).

    Inputs waiting

    Variables

    Output

     
     
     
     
    About Random: the book writes SecretNumber ← Random. In this lab it gives a whole number from 1 to 100. (In real Cambridge pseudocode, RAND(100) gives a real number 0 ≤ x < 100, so you would use INT(RAND(100)) + 1.) Space outputs one space and OUTPUT Newline moves to a new line. A comment containing "without moving to next line" keeps the output on the same line, as in the book.
     
     
      
     
     
    📌 Summary
     
       
    • Abstraction involves filtering out information that is not needed to solve the problem.
      •  
    • Decomposition is breaking problems down into sub-problems, leading to the concept of a program module.
      •  
    • An algorithm is a sequence of steps that can be carried out to solve a problem.
      •  
    • Algorithms are expressed using the four basic constructs of assignment, sequence, selection and repetition.
      •  
    • Algorithms can be documented using pseudocode.
      •  
    • Stepwise refinement: breaking down the steps of an outline solution into smaller and smaller steps.
      •  
    • Logic statements use the relational operators =, <, >, <>, <= and >= and the logic operators AND, OR and NOT.
      •  
    • Selection constructs and conditional loops use conditions to decide which steps are followed.
      •  
     
     
     
    🃏 Key-term flashcards
     
    Tap a card to flip it.
     
     
     
     
    ✅ Quick quiz
     
     
     
     
     
     
    🔢 Modulo-11 practice
     
    For Exam-style Question 1. Weights go 10, 9, 8 … 2 from the left. Work out the check digit, then check.
     
     
     
     
      
     
     
     
    📝 Exam-style questions
     
    Write your answer first, then open the model answer. These are my mark-scheme-style answers, not official mark schemes. Each one runs in the lab.
     
     
    Flowchart for Q1Exam-style question 1: flowchart for the Modulo-11 check digit
     
    Weighting ← 10
Total ← 0
FOR Count ← 1 TO 9
    INPUT Digit
    Value ← Digit * Weighting
    Total ← Total + Value
    Weighting ← Weighting - 1
NEXT Count
Remainder ← Total MOD 11
CheckDigit ← 11 - Remainder
IF CheckDigit = 10
    THEN
        CheckDigit ← "X"
ENDIF
OUTPUT CheckDigit
      
    Mark points: the three initial values · a loop that runs 9 times (FOR, or REPEAT … UNTIL Count = 9 with Count ← Count + 1) · INPUT Digit · Value calculation · running Total · decrement Weighting · Remainder using MOD · CheckDigit ← 11 − Remainder · IF CheckDigit = 10 THEN CheckDigit ← "X".
     
    A flaw in the flowchart: if the remainder is 0, the check digit comes out as 11, which is not a single digit. The real ISBN-10 rule uses CheckDigit ← (11 - Remainder) MOD 11, so it becomes 0. The flowchart also never outputs the check digit; our answer adds OUTPUT CheckDigit.
     
     
     
    PositiveCount ← 0
NegativeCount ← 0
REPEAT
    INPUT Number
    IF Number > 0
        THEN
            PositiveCount ← PositiveCount + 1
    ENDIF
    IF Number < 0
        THEN
            NegativeCount ← NegativeCount + 1
    ENDIF
UNTIL Number = 0
OUTPUT "Positive: ", PositiveCount
OUTPUT "Negative: ", NegativeCount
      
    Mark points: initialise both counts to 0 · REPEAT … UNTIL Number = 0 · INPUT inside the loop · test for positive · increment PositiveCount · test for negative (a separate IF, or ELSE IF, so 0 is counted in neither) · increment NegativeCount.
     
     
     
    Flowchart for Q3Exam-style question 3: flowchart that averages numbers until the rogue value −1
     
    RogueValue ← -1
Total ← 0
Count ← 0
INPUT Number
WHILE Number <> RogueValue DO
    Count ← Count + 1
    Total ← Total + Number
    INPUT Number
ENDWHILE
IF Count > 0
    THEN
        Average ← Total / Count
        OUTPUT Average
ENDIF
      
    Mark points: RogueValue ← −1 · Total and Count ← 0 · first INPUT before the loop · WHILE Number <> RogueValue · increment Count and add to Total · INPUT Number at the end of the loop body · ENDWHILE · IF Count > 0 then calculate and output Average.
     
     
     
     
    Guru Jazzy · Cambridge AS & A Level Computer Science · Chapter 12 Algorithm Design and Problem-Solving · Figures from the Cambridge coursebook (Langfield & Duddell)