Skip to content
Book 8: Algorithms, Programming and Databases

Book 8 · Chapter 9

Algorithm design

§9.1§9.2§9.3Free sample chapterExam craftB8·9

This chapter is being written.

Everything the site already has for it is below — each with the short code the book prints beside it.

For the whole chapter

§9.1 Abstraction

Short code B8·9·1

§9.2 Decomposition

Short code B8·9·2

§9.3 Algorithm design and evaluation

Short code B8·9·3

Abstraction: keep only what matters

Short code B8·9·10

# The model: only what the journey-time question needs
stops = ["Gate", "Library", "Canteen", "Sports hall"]
# minutes from each stop to the next one
minutes = [3, 4, 6]

start = int(input())
finish = int(input())
total = 0
for i in range(start, finish):
    total = total + minutes[i]
print("From", stops[start], "to", stops[finish])
print("Journey time:", total, "minutes")
Abstraction in code: the model keeps only the stops, in order, and the minutes between them — nothing about roads, buildings or the bus itself. Inputs: 0, then 3.

Output

From Gate to Sports hall
Journey time: 13 minutes
Run and checked before printing Run it in the lab

Decomposition: inputs, processes, outputs, storage

Short code B8·9·11

# Storage
houses = ["Red", "Blue", "Green"]
totals = [0, 0, 0]
for event in range(2):
    for house in range(3):
        # Input, checked: 0 to 10 only
        points = int(input())
        while points < 0 or points > 10:
            points = int(input())
        # Process: add to the house total
        totals[house] = totals[house] + points
# Process: find the winner
best = 0
for house in range(1, 3):
    if totals[house] > totals[best]:
        best = house
# Output
for house in range(3):
    print(houses[house], totals[house])
print("Winner:", houses[best])
Decomposition in code: each part of the program is one sub-problem, labelled with what it is. Inputs: 8, 5, 3, then 12 (refused), 7, 6, 4.

Output

Red 15
Blue 11
Green 7
Winner: Red
Run and checked before printing Run it in the lab

Flowcharts: the five symbols

Short code B8·9·12

passes = 0
for i in range(5):
    mark = int(input())
    if mark >= 50:
        passes = passes + 1
print(passes)
The flowchart above, written in Python. Inputs: 62, 48, 50, 91, 35.

Output

3
Run and checked before printing Run it in the lab

Designing and amending an algorithm

Short code B8·9·13

how_many = int(input())        # change 1
passes = 0
fails = 0                      # change 2
for i in range(how_many):      # change 1
    mark = int(input())
    if mark >= 50:
        passes = passes + 1
    else:                      # change 2
        fails = fails + 1
print(passes)
print(fails)                   # change 3
The pass-counting program, amended: the user says how many marks there are, and the number of fails is output too. The three changes are marked with comments. Inputs: 3, then 72, 41, 55.

Output

2
1
Run and checked before printing Run it in the lab

Explaining what an algorithm does

Short code B8·9·14

count = 0
total = 0
while True:
    number = int(input())
    if number == -1:
        break
    if number % 2 == 0:
        total = total + number
        count = count + 1
print(count, total)
Predict first: what is this program for? Test it in your head with the inputs 6, 3, 10, 7, 4, -1.

Output

3 20
Run and checked before printing Run it in the lab

Trace tables

Short code B8·9·15

Output

3 20
Run and checked before printing Run it in the lab
total = 0
for day in range(1, 5):
    steps = int(input())
    if steps >= 8000:
        total = total + 1
        print("Day", day, "target met")
print(total, "days")
The step-counter program as printed in the Trace-it, run with the inputs 9200, 6500, 8000, 12000.

Output

Day 1 target met
Day 3 target met
Day 4 target met
3 days
Run and checked before printing Run it in the lab

Output

1 9200 1 | Day 1 target met
2 6500 - |
3 8000 2 | Day 3 target met
4 12000 3 | Day 4 target met
output: 3 days
Run and checked before printing Run it in the lab

Output

start 4073 0
407 1
40 2
4 3
0 4
output: 4
Run and checked before printing Run it in the lab

Output

start 5 0
3 5
1 8
output: 8
Run and checked before printing Run it in the lab

Finding and fixing errors

Short code B8·9·16

Output

Average: 1.5 Largest: 4
Run and checked before printing Run it in the lab

Output

Average: 7.5 Largest: 10
Run and checked before printing Run it in the lab
total = 0
for n in range(5):
    number = int(input())
    total = total + number
print("Total:", total)
The faded twin's program with its three corrections, run with the inputs 3, 8, 1, 6, 2.

Output

Total: 20
Run and checked before printing Run it in the lab

Linear search

Short code B8·9·17

names = ["Hina", "Ali", "Sara", "Omar", "Zoya"]
target = input()
found = False
index = 0
while index < len(names) and not found:
    if names[index] == target:
        found = True
    else:
        index = index + 1
if found:
    print(target, "found at index", index)
else:
    print(target, "not found")
Linear search with a found flag. The loop stops at the first match, and index is only moved on while nothing has been found. Input: Omar.

Output

Omar found at index 3
Run and checked before printing Run it in the lab
names = ["Hina", "Ali", "Sara", "Omar", "Zoya"]
target = input()
found = False
index = 0
while index < len(names) and not found:
    if names[index] == target:
        found = True
    else:
        index = index + 1
if found:
    print(target, "found at index", index)
else:
    print(target, "not found")
The same search with the input Zara: every name is checked, then the loop ends because index reaches 5.

Output

Zara not found
Run and checked before printing Run it in the lab
codes = [17, 44, 31, 8, 52, 26]
target = int(input())
index = 0
found = False
while True:
    if codes[index] == target:
        found = True
    else:
        index = index + 1
    if found or index == 6:
        break
if found:
    print("Found at", index)
else:
    print("Not found")
The linear-search flowchart above, written in Python. Input: 31.

Output

Found at 2
Run and checked before printing Run it in the lab

Binary search

Short code B8·9·18

nums = [4, 9, 15, 22, 31, 38,
        46, 53, 60, 71, 85]
target = int(input())
low = 0
high = len(nums) - 1
found = False
while low <= high and not found:
    mid = (low + high) // 2
    print(low, high, mid, nums[mid])
    if nums[mid] == target:
        found = True
    elif nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
if found:
    print("Found at index", mid)
else:
    print("Not found")
Binary search, printing low, high, mid and the middle value each time round. Input: 60.

Output

0 10 5 38
6 10 8 60
Found at index 8
Run and checked before printing Run it in the lab

Output

0 10 5 38
0 4 2 15
3 4 3 22
Not found
Run and checked before printing Run it in the lab

Bubble sort

Short code B8·9·19

Output

1 [147, 152, 139, 155, 160] True
2 [147, 139, 152, 155, 160] True
3 [139, 147, 152, 155, 160] True
4 [139, 147, 152, 155, 160] False
Run and checked before printing Run it in the lab

Output

Basic: 16 comparisons
Improved: 10 comparisons
Run and checked before printing Run it in the lab
scores = [23, 8, 15, 4]
swapped = True
while swapped:
    swapped = False
    for i in range(len(scores) - 1):
        if scores[i] > scores[i + 1]:
            temp = scores[i]
            scores[i] = scores[i + 1]
            scores[i + 1] = temp
            swapped = True
print(scores)
The Mark Ladder's bubble sort, run on the scores 23, 8, 15, 4.

Output

[4, 8, 15, 23]
Run and checked before printing Run it in the lab
names = ["Musa", "Alia", "Zain", "Dua"]
swapped = True
while swapped:
    swapped = False
    for i in range(len(names) - 1):
        if names[i] < names[i + 1]:
            temp = names[i]
            names[i] = names[i + 1]
            names[i + 1] = temp
            swapped = True
print(names)
The faded twin's sort, descending, on the names Musa, Alia, Zain, Dua.

Output

['Zain', 'Musa', 'Dua', 'Alia']
Run and checked before printing Run it in the lab

Insertion sort

Short code B8·9·20

Output

insert 12 [12, 31, 47, 5, 26, 19]
insert 47 [12, 31, 47, 5, 26, 19]
insert 5 [5, 12, 31, 47, 26, 19]
insert 26 [5, 12, 26, 31, 47, 19]
insert 19 [5, 12, 19, 26, 31, 47]
Run and checked before printing Run it in the lab

Merge sort

Short code B8·9·21

Output

[41, 18, 66, 7, 53, 29, 12, 90]
[41, 18, 66, 7] [53, 29, 12, 90]
[41, 18] [66, 7] [53, 29] [12, 90]
[41] [18] [66] [7] [53] [29] [12] [90]
[18, 41] [7, 66] [29, 53] [12, 90]
[7, 18, 41, 66] [12, 29, 53, 90]
[7, 12, 18, 29, 41, 53, 66, 90]
Run and checked before printing Run it in the lab

Comparing algorithms

Short code B8·9·22

Output

3 3 8
500 500 1
1000 1000 10
Run and checked before printing Run it in the lab

Command-word coach

Short code B8·9·23

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

Workbook: Algorithm design

Short code W8·9 · Algorithms, Programming and Databases 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 W8·9·K

Data files and skeleton code in Python for this chapter's tasks arrive here with the chapter.

Ask Z about Algorithm design
Enroll nowOnline classes