Skip to content
Book 6: Algorithms, Programming and Logic

Book 6 · Chapter 7

Algorithm design and problem-solving

§7Free sample chapterBanker · ≈ 22.8 m · →B6·7

This chapter is free to read here.

Read it in full on cswithzak.com — every question with its mark scheme, every program ready to run. The free practice for each section is below, with the short code the book prints beside it.

Read it free

For the whole chapter

§7

Short code B6·7·1

The program development life cycle

Short code B6·7·10

Practice for this page of the book: the quiz, flashcards and past-paper questions for its section are listed above.

Systems, sub-systems and structure diagrams

Short code B6·7·11

Practice for this page of the book: the quiz, flashcards and past-paper questions for its section are listed above.

Flowcharts and pseudocode, written precisely

Short code B6·7·12

DECLARE Temp : INTEGER
DECLARE HotDays : INTEGER
HotDays ← 0
INPUT Temp
WHILE Temp <> 999 DO
    IF Temp > 30
      THEN
        HotDays ← HotDays + 1
    ENDIF
    INPUT Temp
ENDWHILE
OUTPUT "Hot days: ", HotDays
The flowchart above as pseudocode. The value 999 is a rogue value: it is not a temperature, it only tells the loop to stop. Lines beginning › are the values typed in.

Output

› 28
› 33
› 31
› 25
› 999
Hot days: 2
Run and checked before printing Run it in the lab

The purpose of an algorithm

Short code B6·7·13

DECLARE Number : INTEGER
DECLARE Digits : INTEGER
Number ← 40731
Digits ← 0
REPEAT
    Number ← DIV(Number, 10)
    Digits ← Digits + 1
UNTIL Number = 0
OUTPUT Digits
Predict: what does this algorithm output?
Run and checked before printing Run it in the lab

Totalling, counting, maximum, minimum and average

Short code B6·7·14

DECLARE Steps : ARRAY[1:7] OF INTEGER
DECLARE Day : INTEGER
DECLARE Total : INTEGER
DECLARE BigDays : INTEGER
DECLARE Highest : INTEGER
DECLARE Lowest : INTEGER
DECLARE Average : REAL
Steps[1] ← 6240
Steps[2] ← 9105
Steps[3] ← 7380
Steps[4] ← 4512
Steps[5] ← 10233
Steps[6] ← 8450
Steps[7] ← 5679
Total ← 0
BigDays ← 0
Highest ← Steps[1]
Lowest ← Steps[1]
FOR Day ← 1 TO 7
    Total ← Total + Steps[Day]
    IF Steps[Day] > 8000
      THEN
        BigDays ← BigDays + 1
    ENDIF
    IF Steps[Day] > Highest
      THEN
        Highest ← Steps[Day]
    ENDIF
    IF Steps[Day] < Lowest
      THEN
        Lowest ← Steps[Day]
    ENDIF
NEXT Day
Average ← Total / 7
OUTPUT "Total: ", Total
OUTPUT "Days over 8000: ", BigDays
OUTPUT "Highest: ", Highest, " Lowest: ", Lowest
OUTPUT "Average: ", ROUND(Average, 1)
One loop, five standard methods: totalling (Total), counting (BigDays), maximum, minimum and the average after the loop.

Output

Total: 51599
Days over 8000: 3
Highest: 10233 Lowest: 4512
Average: 7371.3
Run and checked before printing Run it in the lab
Steps = [6240, 9105, 7380, 4512, 10233, 8450, 5679]
Total = 0
BigDays = 0
Highest = Steps[0]
Lowest = Steps[0]
for Day in range(7):
    Total = Total + Steps[Day]
    if Steps[Day] > 8000:
        BigDays = BigDays + 1
    if Steps[Day] > Highest:
        Highest = Steps[Day]
    if Steps[Day] < Lowest:
        Lowest = Steps[Day]
Average = Total / 7
print("Total:", Total)
print("Days over 8000:", BigDays)
print("Highest:", Highest, "Lowest:", Lowest)
print("Average:", round(Average, 1))
The same algorithm in Python, VB.NET and Java. Each language counts list positions from 0, so the loop runs 0 to 6.

Output

Total: 51599
Days over 8000: 3
Highest: 10233 Lowest: 4512
Average: 7371.3
Run and checked before printing Run it in the lab

Linear search

Short code B6·7·15

DECLARE Names : ARRAY[1:6] OF STRING
DECLARE Target : STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
Names[1] ← "Bilal"
Names[2] ← "Chen"
Names[3] ← "Dina"
Names[4] ← "Emeka"
Names[5] ← "Farah"
Names[6] ← "Gul"
Target ← "Emeka"
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 6 DO
    IF Names[Index] = Target
      THEN
        Found ← TRUE
      ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT Target, " found at position ", Index
  ELSE
    OUTPUT Target, " not found"
ENDIF
A linear search with a flag. The loop stops at the first match, so Index still holds the position when the loop ends.

Output

Emeka found at position 4
Run and checked before printing Run it in the lab
Names = ["Bilal", "Chen", "Dina", "Emeka", "Farah", "Gul"]
Target = "Emeka"
Found = False
Index = 0
while Found == False and Index < 6:
    if Names[Index] == Target:
        Found = True
    else:
        Index = Index + 1
if Found == True:
    print(Target, "found at position", Index + 1)
else:
    print(Target, "not found")
The search in three languages. The list starts at position 0, so each program adds 1 before it reports the position.

Output

Emeka found at position 4
Run and checked before printing Run it in the lab

Bubble sort

Short code B6·7·16

DECLARE Times : ARRAY[1:5] OF INTEGER
DECLARE Index : INTEGER
DECLARE Temp : INTEGER
DECLARE Swapped : BOOLEAN
DECLARE Last : INTEGER
Times[1] ← 52
Times[2] ← 47
Times[3] ← 61
Times[4] ← 39
Times[5] ← 50
Last ← 4
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Last
        IF Times[Index] > Times[Index + 1]
          THEN
            Temp ← Times[Index]
            Times[Index] ← Times[Index + 1]
            Times[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Last ← Last - 1
UNTIL Swapped = FALSE OR Last = 0
FOR Index ← 1 TO 5
    OUTPUT Times[Index]
NEXT Index
The whole bubble sort: five lap times into ascending order, then output.

Output

39
47
50
52
61
Run and checked before printing Run it in the lab
Times = [52, 47, 61, 39, 50]
Last = 3
Swapped = True
while Swapped == True and Last >= 0:
    Swapped = False
    for I in range(0, Last + 1):
        if Times[I] > Times[I + 1]:
            Temp = Times[I]
            Times[I] = Times[I + 1]
            Times[I + 1] = Temp
            Swapped = True
    Last = Last - 1
for I in range(5):
    print(Times[I])
The same bubble sort in Python, VB.NET and Java. Lists start at position 0 here, and the loop counter is called I to keep the lines short.

Output

39
47
50
52
61
Run and checked before printing Run it in the lab

Validation and verification

Short code B6·7·17

DECLARE Age : INTEGER
REPEAT
    OUTPUT "Enter age (11 to 18)"
    INPUT Age
    IF Age < 11 OR Age > 18
      THEN
        OUTPUT "Out of range, try again"
    ENDIF
UNTIL Age >= 11 AND Age <= 18
OUTPUT "Accepted: ", Age
A range check inside a loop: the age is input again until it is from 11 to 18.

Output

Enter age (11 to 18)
› 9
Out of range, try again
Enter age (11 to 18)
› 19
Out of range, try again
Enter age (11 to 18)
› 14
Accepted: 14
Run and checked before printing Run it in the lab
DECLARE Password : STRING
REPEAT
    OUTPUT "Choose a password (8 or more characters)"
    INPUT Password
    IF Password = ""
      THEN
        OUTPUT "Nothing was entered"
      ELSE
        IF LENGTH(Password) < 8
          THEN
            OUTPUT "Too short"
        ENDIF
    ENDIF
UNTIL LENGTH(Password) >= 8
OUTPUT "Password set"
A presence check, then a length check, on the same input. LENGTH counts the characters.

Output

Choose a password (8 or more characters)
›
Nothing was entered
Choose a password (8 or more characters)
› lion42
Too short
Choose a password (8 or more characters)
› lantern42
Password set
Run and checked before printing Run it in the lab
DECLARE Laps : REAL
REPEAT
    OUTPUT "Laps swum today?"
    INPUT Laps
    IF Laps <> ROUND(Laps, 0)
      THEN
        OUTPUT "Count whole laps only"
    ENDIF
UNTIL Laps = ROUND(Laps, 0)
OUTPUT "Logged ", Laps, " laps"
A type check for a whole number: a value that changes when it is rounded to 0 decimal places has a fractional part.

Output

Laps swum today?
› 2.5
Count whole laps only
Laps swum today?
› 3
Logged 3 laps
Run and checked before printing Run it in the lab
DECLARE Code : STRING
DECLARE Symbol : STRING
DECLARE Position : INTEGER
DECLARE Valid : BOOLEAN
REPEAT
    OUTPUT "Locker code (e.g. AB123)"
    INPUT Code
    Valid ← TRUE
    IF LENGTH(Code) <> 5
      THEN
        Valid ← FALSE
      ELSE
        FOR Position ← 1 TO 5
            Symbol ← SUBSTRING(Code, Position, 1)
            IF Position <= 2
              THEN
                IF Symbol < "A" OR Symbol > "Z"
                  THEN
                    Valid ← FALSE
                ENDIF
              ELSE
                IF Symbol < "0" OR Symbol > "9"
                  THEN
                    Valid ← FALSE
                ENDIF
            ENDIF
        NEXT Position
    ENDIF
    IF Valid = FALSE
      THEN
        OUTPUT "Wrong format"
    ENDIF
UNTIL Valid = TRUE
OUTPUT "Code accepted: ", Code
A format check: two capital letters then three digits. SUBSTRING(Code, Position, 1) picks out one character at a time.

Output

Locker code (e.g. AB123)
› AB12
Wrong format
Locker code (e.g. AB123)
› A1234
Wrong format
Locker code (e.g. AB123)
› AB123
Code accepted: AB123
Run and checked before printing Run it in the lab
DECLARE Number : INTEGER
DECLARE Total : INTEGER
DECLARE Weight : INTEGER
DECLARE Position : INTEGER
DECLARE CheckDigit : INTEGER
Number ← 47215
Total ← 0
Weight ← 3
FOR Position ← 1 TO 5
    Total ← Total + MOD(Number, 10) * Weight
    Number ← DIV(Number, 10)
    IF Weight = 3
      THEN
        Weight ← 1
      ELSE
        Weight ← 3
    ENDIF
NEXT Position
CheckDigit ← MOD(10 - MOD(Total, 10), 10)
OUTPUT "Total: ", Total
OUTPUT "Check digit: ", CheckDigit
Working out a check digit. MOD(Number, 10) is the last digit; DIV(Number, 10) removes it. The weights alternate 3, 1, 3, 1, 3.

Output

Total: 41
Check digit: 9
Run and checked before printing Run it in the lab
DECLARE Email : STRING
DECLARE Again : STRING
REPEAT
    OUTPUT "Enter your email"
    INPUT Email
    OUTPUT "Enter it again"
    INPUT Again
    IF Email <> Again
      THEN
        OUTPUT "They do not match, start again"
    ENDIF
UNTIL Email = Again
OUTPUT "Saved: ", Email
A double entry check: the two copies must match before the email is stored.

Output

Enter your email
› sam@mail.com
Enter it again
› sam@mial.com
They do not match, start again
Enter your email
› sam@mail.com
Enter it again
› sam@mail.com
Saved: sam@mail.com
Run and checked before printing Run it in the lab

Test data

Short code B6·7·18

DECLARE Test : ARRAY[1:7] OF INTEGER
DECLARE Index : INTEGER
Test[1] ← 14
Test[2] ← 11
Test[3] ← 18
Test[4] ← 10
Test[5] ← 19
Test[6] ← 40
Test[7] ← -5
FOR Index ← 1 TO 7
    IF Test[Index] >= 11 AND Test[Index] <= 18
      THEN
        OUTPUT Test[Index], " accepted"
      ELSE
        OUTPUT Test[Index], " rejected"
    ENDIF
NEXT Index
Seven test values run through the rule whole number from 11 to 18. The program does what the test plan predicts.

Output

14 accepted
11 accepted
18 accepted
10 rejected
19 rejected
40 rejected
-5 rejected
Run and checked before printing Run it in the lab

Trace tables and finding errors

Short code B6·7·19

DECLARE Number : INTEGER
DECLARE Total : INTEGER
DECLARE Threes : INTEGER
Total ← 0
Threes ← 0
OUTPUT "Number? (0 to stop)"
INPUT Number
WHILE Number <> 0 DO
    Total ← Total + Number
    IF MOD(Number, 3) = 0
      THEN
        Threes ← Threes + 1
    ENDIF
    OUTPUT "Number? (0 to stop)"
    INPUT Number
ENDWHILE
OUTPUT Total, " ", Threes
The program traced above, run with the inputs 9, 4, 12 and 0. The prompt is output before every input; lines beginning › are the values typed in.

Output

Number? (0 to stop)
› 9
Number? (0 to stop)
› 4
Number? (0 to stop)
› 12
Number? (0 to stop)
› 0
25 2
Run and checked before printing Run it in the lab
Prompt = "Number? (0 to stop)"
Total = 0
Threes = 0
print(Prompt)
Number = int(input())
while Number != 0:
    Total = Total + Number
    if Number % 3 == 0:
        Threes = Threes + 1
    print(Prompt)
    Number = int(input())
print(Total, Threes)
The traced program in three languages, given the same four inputs. A program does not echo what you type, so only the prompts and the result appear.

Output

Number? (0 to stop)
Number? (0 to stop)
Number? (0 to stop)
Number? (0 to stop)
25 2
Run and checked before printing Run it in the lab
DECLARE Mark : INTEGER
DECLARE Highest : INTEGER
DECLARE Total : INTEGER
DECLARE Count : INTEGER
Highest ← 100
Total ← 0
FOR Count ← 1 TO 4
    INPUT Mark
    Total ← Total + Count
    IF Mark > Highest
      THEN
        Highest ← Mark
    ENDIF
NEXT Count
OUTPUT "Highest: ", Highest
OUTPUT "Average: ", Total / 5
The faulty algorithm, run with five marks typed in. It runs without stopping, but look at the results: only four marks are read and both answers are wrong.

Output

› 55
› 72
› 64
› 81
Highest: 100
Average: 2
Run and checked before printing Run it in the lab

Output

› 55
› 72
› 64
› 81
› 49
Highest: 81
Average: 64.2
Run and checked before printing Run it in the lab

Writing and amending algorithms

Short code B6·7·20

DECLARE Drink : ARRAY[1:4] OF STRING
DECLARE Sold : ARRAY[1:4] OF INTEGER
DECLARE Code : CHAR
DECLARE Item : INTEGER
DECLARE Total : INTEGER
DECLARE Best : INTEGER
Drink[1] ← "Tea"
Drink[2] ← "Coffee"
Drink[3] ← "Juice"
Drink[4] ← "Water"
FOR Item ← 1 TO 4
    Sold[Item] ← 0
NEXT Item
Total ← 0
INPUT Code
WHILE Code <> 'X' DO
    CASE OF Code
      'T' : Item ← 1
      'C' : Item ← 2
      'J' : Item ← 3
      'W' : Item ← 4
      OTHERWISE Item ← 0
    ENDCASE
    IF Item = 0
      THEN
        OUTPUT "Invalid code"
      ELSE
        Sold[Item] ← Sold[Item] + 1
        Total ← Total + 1
    ENDIF
    INPUT Code
ENDWHILE
Best ← 1
FOR Item ← 1 TO 4
    OUTPUT Drink[Item], ": ", Sold[Item]
    IF Sold[Item] > Sold[Best]
      THEN
        Best ← Item
    ENDIF
NEXT Item
OUTPUT "Drinks sold: ", Total
OUTPUT "Most popular: ", Drink[Best]
The café program. It validates every code, counts each drink in its own array element, totals the drinks and finds the most popular.

Output

› T
› C
› J
› T
› W
› Q
Invalid code
› T
› C
› X
Tea: 3
Coffee: 2
Juice: 1
Water: 1
Drinks sold: 7
Most popular: Tea
Run and checked before printing Run it in the lab
Drink = ["Tea", "Coffee", "Juice", "Water"]
Sold = [0, 0, 0, 0]
Total = 0
Code = input()
while Code != "X":
    if Code == "T":
        Item = 0
    elif Code == "C":
        Item = 1
    elif Code == "J":
        Item = 2
    elif Code == "W":
        Item = 3
    else:
        Item = -1
    if Item == -1:
        print("Invalid code")
    else:
        Sold[Item] = Sold[Item] + 1
        Total = Total + 1
    Code = input()
Best = 0
for Item in range(4):
    print(Drink[Item] + ":", Sold[Item])
    if Sold[Item] > Sold[Best]:
        Best = Item
print("Drinks sold:", Total)
print("Most popular:", Drink[Best])
The café program in Python, VB.NET and Java, given the same codes. Python uses if … elif, VB.NET Select Case and Java switch where the pseudocode uses CASE.

Output

Invalid code
Tea: 3
Coffee: 2
Juice: 1
Water: 1
Drinks sold: 7
Most popular: Tea
Run and checked before printing Run it in the lab
DECLARE Temp : INTEGER
DECLARE HotDays : INTEGER
DECLARE Day : INTEGER
HotDays ← 0
FOR Day ← 1 TO 7
    INPUT Temp
    IF Temp > 30
      THEN
        HotDays ← HotDays + 1
    ENDIF
NEXT Day
OUTPUT "Hot days: ", HotDays
Amended: a count-controlled loop for exactly seven days. The rogue value has gone, and so has the INPUT before the loop.

Output

› 29
› 31
› 34
› 30
› 27
› 33
› 28
Hot days: 3
Run and checked before printing Run it in the lab

Command-word coach

Short code B6·7·21

Practice for this page of the book: the quiz, flashcards and past-paper questions for its section are listed above.

Workbook: Algorithm design and problem-solving

Short code W6·7 · Algorithms, Programming and Logic Workbook

The write-in workbook for this chapter — drills, exam-style practice, trace tables, fix-the-mistake and mark-it-yourself pages. Its full mark schemes and an interactive version arrive here with the chapter.

Starter files

Short code W6·7·K

Data files and skeleton code in Pseudocode, Python, VB.NET, Java for this chapter's tasks arrive here with the chapter.

Ask Z about Algorithm design and problem-solving
Enroll nowOnline classes