Year 10 · Computer Science · Spring 2

Algorithm design and problem solving · Lesson 3 of 5

Standard methods: totals, counts, max, min, average

Practical7.4 Standard methods of solution

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

You will learn to

  • Write totalling and counting in pseudocode and in Python.
  • Write an algorithm to find the maximum, minimum and average of a set of values.
  • Explain why the starting values of the total, maximum and minimum matter.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Success criteria

You have got it when you can say:

  • I can write a total and a count from memory, in both languages.
  • I can find the biggest value with a loop, and check it in the trace toy.
  • I can explain why the maximum should start at the first value, not at 0.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Retrieval starter

Questions from before. Write your answers, then show them.

  1. Last lesson

    Abnormal test data is…

    A Typical dataB Data that should be rejectedC Data at the edge of the range

    B. Data that should be rejected

  2. Last unit

    A MAC address is…

    A The fixed hardware address of a network cardB The name of a websiteC Given out by the router each time

    A. The fixed hardware address of a network card

  3. Earlier this year

    A range check on age 0 to 120 would reject…

    A 0B 150C 120

    B. 150

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Key words (1 of 3)

Program development life cycle
The four stages of making a program: analysis, design, coding and testing.
Pseudocode
A structured, code-like way of writing an algorithm that is not tied to one language.
Totalling
Adding values into a running total, for example Total ← Total + Value.
Counting
Adding 1 to a counter each time something happens.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Key words (2 of 3)

Linear search
Checking each item in a list in turn until the target is found or the list ends.
Bubble sort
Sorting by comparing neighbouring items and swapping them if they are in the wrong order, pass after pass.
Check digit
An extra digit calculated from the other digits, used to catch typing errors.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Key words (3 of 3)

Trace table
A table used in a dry run to record the value of each variable as an algorithm runs.

The explanation · step 1 of 6 · part 1 of 5

Totalling and counting

Totalling means adding values into a running total: `Total ← Total + Value`.

Counting means adding 1 each time something happens: `Count ← Count + 1`.

Both variables must start at 0 before the loop.

The explanation · step 1 of 6 · part 2 of 5

Totalling and counting (continued)

e.g.Example
Marks 34, 48, 21, 40, 15, 45. Pass mark 25. Total: 0 → 34 → 82 → 103 → 143 → 158 → 203 PassCount: 34 yes (1), 48 yes (2), 21 no, 40 yes (3), 15 no, 45 yes (4) Output: Total: 203, Number of passes: 4

The explanation · step 1 of 6 · part 3 of 5

Totalling and counting (continued)

DECLARE Marks : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE Total : INTEGER
DECLARE PassCount : INTEGER
// Marks already holds 34, 48, 21, 40, 15, 45
Total ← 0
PassCount ← 0
FOR Index ← 1 TO 6
  Total ← Total + Marks[Index]
  IF Marks[Index] >= 25
    THEN
      PassCount ← PassCount + 1
  ENDIF
NEXT Index
OUTPUT "Total: ", Total
OUTPUT "Number of passes: ", PassCount

The explanation · step 1 of 6 · part 4 of 5

Totalling and counting (continued)

marks = [34, 48, 21, 40, 15, 45]
total = 0
pass_count = 0
for index in range(6):
    total = total + marks[index]
    if marks[index] >= 25:
        pass_count = pass_count + 1
print("Total:", total)
print("Number of passes:", pass_count)

The explanation · step 1 of 6 · part 5 of 5

Totalling and counting (continued)

!Watch out

Setting Total to 0 inside the loop is a classic error. The total is wiped each time round, so only the last value is kept.

The explanation · step 2 of 6 · part 1 of 6

Finding the maximum and minimum

To find the maximum (largest), keep a variable `Highest`. Compare each value with it. If the value is bigger, it becomes the new `Highest`.

The minimum (smallest) works the same way with `Lowest` and `<`.

Start `Highest` at the smallest possible value and `Lowest` at the largest possible value. Another safe way is to start both at the first item.

The explanation · step 2 of 6 · part 2 of 6

Finding the maximum and minimum (continued)

e.g.Example
Marks out of 50: 34, 48, 21, 40, 15, 45. Highest: 0 → 34 → 48 (21, 40, 15, 45 are not bigger than 48) Lowest: 50 → 34 → 21 → 15 (40, 45 are not smaller than 15) Output: Highest: 48, Lowest: 15

The explanation · step 2 of 6 · part 3 of 6

Finding the maximum and minimum (continued)

DECLARE Marks : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE Highest : INTEGER
DECLARE Lowest : INTEGER
// Marks already holds 34, 48, 21, 40, 15, 45 (each out of 50)
Highest ← 0
Lowest ← 50

The explanation · step 2 of 6 · part 4 of 6

Finding the maximum and minimum (continued)

FOR Index ← 1 TO 6
  IF Marks[Index] > Highest
    THEN
      Highest ← Marks[Index]
  ENDIF
  IF Marks[Index] < Lowest
    THEN
      Lowest ← Marks[Index]
  ENDIF
NEXT Index
OUTPUT "Highest: ", Highest
OUTPUT "Lowest: ", Lowest

The explanation · step 2 of 6 · part 5 of 6

Finding the maximum and minimum (continued)

marks = [34, 48, 21, 40, 15, 45]
highest = 0
lowest = 50
for index in range(6):
    if marks[index] > highest:
        highest = marks[index]
    if marks[index] < lowest:
        lowest = marks[index]
print("Highest:", highest)
print("Lowest:", lowest)

The explanation · step 2 of 6 · part 6 of 6

Finding the maximum and minimum (continued)

!Watch out

If Lowest starts at 0, no mark is ever smaller, so the answer is wrong. Start Lowest at the top of the range (50 here) or at the first value.

The explanation · 4 more steps

More on the lesson page

The lesson page has the rest of the explanation, step by step:

  • Finding the average
  • Linear search
  • Bubble sort
  • How many comparisons? (extra)

Open the lesson page

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Try it: Trace 'find the biggest'

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Quick quiz · 1 of 3

Typing an email address twice to check it is…

  1. A Verification
  2. B Validation
  3. C A trace table

A. Verification

Validation checks the data is sensible; verification checks it was entered as intended.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Quick quiz · 2 of 3

In a trace table you write a new row…

  1. A Only at the end
  2. B Only for OUTPUT
  3. C Each time a value changes

C. Each time a value changes

One column per variable, one row per change.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Quick quiz · 3 of 3

A diamond in a flowchart means…

  1. A Input or output
  2. B A process
  3. C A decision

C. A decision

Rectangle: process. Parallelogram: input or output. Diamond: a question with yes and no.

Year 10 · Computer Science · Algorithm design and problem solving · Lesson 3 of 5

Exit ticket

Answer on paper before you go. Then check.

  1. Bubble sort stops when…

    A Half the list is sortedB The first swap happensC A whole pass makes no swaps

    C. A whole pass makes no swaps No swaps in a pass means everything is in order.

  2. The four stages of the program development life cycle are…

    A Input, process, output, storageB Analysis, design, coding, testingC Fetch, decode, execute, store

    B. Analysis, design, coding, testing Analyse the problem, design the solution, write the code, test it.