Ch 2 · 7 Algorithm Design: Standard Methods of Solution · O Level Computer Science 2210
Topic 2 of 4 in Algorithm Design and Problem-Solving — O Level Computer Science 2210 — 59 lessons.
Introduction
Many problems are solved with the same few building blocks: adding up, counting, finding the biggest or smallest, searching a list and sorting it. Learn these standard methods and you can combine them to solve most exam algorithms. (Syllabus topic 7, outcome 4.)
Key ideas — Totalling
Keep a running total: set it to zero, then add each value.
🧑🏫 Teacher's explanation
Imagine you are standing at a ticket booth at a cinema. Every time a person walks through the door, you click a handheld tally counter. You aren't interested in who the people are or what they are wearing; you only care about the final number on that counter. This is exactly what 'totalling' does in programming.
📖 Definitions
🔍 Worked example — Easy
A program uses a loop to input 5 integers. Trace the value of Total if the inputs are 10, 5, 20, 2, and 3.
🔍 Worked example — Standard
Write pseudocode to calculate the total of all even numbers in an array Numbers of size n.
🔍 Worked example — Exam-style
An algorithm calculates the total of 100 numbers. If the sum of the first 99 numbers is 4500 and the 100th number is 50, what is the final value of Total?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Write pseudocode to calculate the total cost of all items in the basket. (3 marks) [3 marks]
Key ideas — Counting
Keep a counter: set it to zero, then add 1 each time something happens.
🧑🏫 Teacher's explanation
Imagine you are standing at the entrance of a cinema. Your only job is to count how many people enter. You don't care about their names, their age, or what movie they are seeing; you just keep a mental tally. Every time a person walks through the door, you increment your tally by one. This is exactly what a 'counter' does in programming.
📖 Definitions
🔍 Worked example — Easy
A list of 5 exam scores is provided: 45, 72, 30, 88, 55. Write pseudocode to count how many scores are 50 or greater.
🔍 Worked example — Standard
Trace the following pseudocode for the input sequence: 10, 20, 10, 30, 10. Output the final value of 'Count'.
🔍 Worked example — Exam-style
An algorithm counts how many numbers in a list of size N are prime. The current value of PrimeCount is 4. A new number, 7, is processed. What is the new value of PrimeCount?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — Maximum, minimum and average
Start the maximum and minimum at the first value (or at values that any real value will beat), then compare each new value.
🧑🏫 Teacher's explanation
Imagine you are a scout looking for the tallest person in a line of students. You don't know how tall anyone is until you see them. So, you look at the first student and say, "You are currently the tallest I've seen." As you move down the line, you compare every new person to your current 'tallest' record. If a new person is taller, they become your new record. You do the same for the shortest person.
📖 Definitions
🔍 Worked example — Easy
Find the maximum and minimum in the set: 12, 5, 22, 8, 15.
🔍 Worked example — Standard
Calculate the average of the following numbers: 10, 20, 30, 40, 50.
🔍 Worked example — Exam-style
A program uses a loop to process 5 numbers. The values entered are 7, 3, 9, 1, 5. The algorithm initializes Total arrow 0 and Count arrow 0. Trace the final value of Total and Average.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — Linear search
A linear search checks each item in turn, from the start of a list, until it finds the target or reaches the end.
🧑🏫 Teacher's explanation
Imagine you are looking for a specific book in a messy pile of books on a floor. You don't know where it is, so you pick up the first book, check the title, and if it's not the one, you put it aside and pick up the second. You keep doing this, one by one, until you either find your book or realize there are no more books left in the pile.
📖 Definitions
🔍 Worked example — Easy
A list contains the following integers: [12, 45, 7, 23, 56]. Perform a linear search for the value 23. Trace the number of comparisons made.
🔍 Worked example — Standard
A list of 5 names is stored in an array: ['Alice', 'Bob', 'Charlie', 'David', 'Eve']. A linear search is performed for 'Eve'. How many iterations of the loop occur?
🔍 Worked example — Exam-style
A linear search is performed on a list of n elements. What is the worst-case number of comparisons required to find an element that is not in the list?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
a) State the name of the standard searching method that should be used. [1] b) Write pseudocode for a function SearchID(IDList, TargetID) that returns TRUE if the TargetID is found in IDList and FALSE otherwise. [4] [5 marks]
Key ideas — Bubble sort
A bubble sort puts items into order by repeatedly comparing adjacent pairs and swapping them if they are in the wrong order. After each pass, the largest remaining item has "bubbled" to the end. It stops when a pass makes no swaps.
🧑🏫 Teacher's explanation
Imagine a line of students of different heights trying to stand in order from shortest to tallest. You start at the beginning of the line and compare the first two students. If the first one is taller than the second, they swap places. Then you move to the next pair (the 2nd and 3rd student) and do the same. You keep doing this until you reach the end of the line. By the time you finish one full trip down the line, the tallest student has 'bubbled' up to the very last position.
📖 Definitions
🔍 Worked example — Easy
Trace one full pass of a bubble sort on the array: [5, 2, 9, 1, 6].
🔍 Worked example — Standard
Determine the number of comparisons required to sort an array of 10 elements in the worst-case scenario using a standard bubble sort.
🔍 Worked example — Exam-style
A list contains [12, 7, 12, 5]. How many swaps occur in the first pass of a bubble sort?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Write pseudocode for the inner loop of the bubble sort that compares adjacent elements and swaps them if they are in the wrong order. [3] (b) Explain why a temporary variable is required during the swap process. [2] [5 marks]
Worked example
Write an algorithm that inputs 20 temperatures and outputs how many were below 0 and the average temperature.
🔍 Worked example — Easy
Write an algorithm to input 5 integers and output the total sum.
🔍 Worked example — Standard
An algorithm inputs 10 numbers. It outputs how many numbers are greater than 50.
🔍 Worked example — Exam-style
Write an algorithm that inputs 15 temperatures (REAL). It must output the average temperature and the number of temperatures that were exactly 37.0 degrees.
⚠️ Common errors
Common mistakes
Practice
Answers: (1) 7,2 swap → 2 7 9 4; 7,9 no swap; 9,4 swap → 2 7 4 9. (2) Count ← 0 / FOR Index ← 1 TO 50 / IF MOD(Numbers[Index], 2) = 0 THEN Count ← Count + 1 ENDIF / NEXT Index / OUTPUT Count. (3) It checks every item in turn from the start, so the order does not matter. (4) Lowest ← Prices[1] / FOR Index ← 2 TO 100 / IF Prices[Index] < Lowest THEN Lowest ← Prices[Index] ENDIF / NEXT Index / OUTPUT Lowest.