Ch 1 · 9 Algorithm Design and Problem-Solving · AS & A Level Computer Science 9618
Topic 1 of 3 in Algorithms, Data Structures and Programming — AS & A Level Computer Science 9618 — 79 lessons.
Introduction
Before writing a program, you must understand the problem and design a solution. This lesson covers the two key thinking skills, abstraction and decomposition, and the three ways of writing an algorithm: structured English, flowcharts and pseudocode. (Syllabus topic 9: sections 9.1–9.2.)
Key ideas — 9.1 (a) Abstraction
Abstraction means removing unnecessary detail and keeping only the details that are essential to solving the problem.
🧑🏫 Teacher's explanation
Imagine you are looking at a map of a subway system. To get from one station to another, you only care about the station names, the lines (colors), and how they connect. You don't care about the exact GPS coordinates of every brick in the tunnel, the color of the tiles on the platform, or how many people are currently standing on the train.
📖 Definitions
🔍 Worked example — Easy
Identify the essential details for an abstract model of a 'Student Management System' used to track exam grades.
🔍 Worked example — Standard
A developer is designing a flight booking system. Which of the following is an example of abstraction?
🔍 Worked example — Exam-style
A programmer uses decomposition to break down the problem 'Create a Video Game'. They identify three sub-problems: 'Player Movement', 'Enemy AI', and 'Score Tracking'. If the 'Player Movement' sub-problem is further broken down into 'Handle Keyboard Input' and 'Update Player Coordinates', what technique is being used?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Define the term 'abstraction'. [2] (b) Describe how abstraction could be used when designing the 'Book' entity in this system. [2] [4 marks]
Key ideas — 9.1 (b) Decomposition
Decomposition means breaking a problem down into smaller sub-problems, each of which is easier to solve. Sub-problems can be broken down further until each one is a single task.
🧑🏫 Teacher's explanation
Imagine you are tasked with organizing a massive music festival. If you try to plan the entire event in one single, giant checklist, you will likely miss details or become overwhelmed. Instead, you break it down: one team handles the stage setup, another handles ticket sales, and a third handles security. Each of these is a 'sub-problem'.
📖 Definitions
🔍 Worked example — Easy
Decompose the problem: 'Calculate the average grade of a class of students'.
🔍 Worked example — Standard
A program needs to 'Process a Library Return'. Decompose this into three specific modules (procedures/functions).
🔍 Worked example — Exam-style
A developer is writing a game. The main loop handles 'Game Logic'. Decompose 'Game Logic' into four distinct modules and explain the benefit of this decomposition.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Decompose the 'Automated Car Wash' problem into four distinct sub-problems. [4] (b) State one advantage of decomposing this system into modules. [1] [5 marks]
Key ideas — 9.2 (a) Algorithms and identifier tables
An algorithm is a solution to a problem expressed as a sequence of defined steps.
🧑🏫 Teacher's explanation
Imagine you are writing a recipe for a complex cake. If you just write "mix stuff," it is useless. You need a sequence of specific steps: "crack 3 eggs," "add 200g flour," etc. In computer science, this sequence is an algorithm. To make sure anyone (or any computer) can follow it without confusion, you need a clear list of ingredients and their measurements before you start.
📖 Definitions
🔍 Worked example — Easy
Create an identifier table for an algorithm that calculates the average of 10 test scores.
🔍 Worked example — Standard
Convert the following structured English into pseudocode: "Input a number N. If N is positive, output 'Positive', otherwise output 'Negative'."
🔍 Worked example — Exam-style
An algorithm uses a variable Price (REAL) and TaxRate (REAL). Write the pseudocode to calculate and output the TotalCost (REAL) including a 15\% tax.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Draw an identifier table for the variables required. [2] (b) Write the pseudocode for this algorithm. [4] [6 marks]
Key ideas — 9.2 (b) Input, process, output and the three constructs
Every algorithm uses three basic constructs:
🧑🏫 Teacher's explanation
Think of an algorithm like a recipe for baking a cake. First, you gather your ingredients (Input). Then, you follow a specific order: crack the eggs, mix the flour, bake in the oven (Sequence). Sometimes, you have to make a choice, like 'IF the oven is too hot, THEN turn it down' (Selection). Finally, if you are making 12 cupcakes, you might repeat the scooping process 12 times (Iteration). Once finished, you serve the cake (Output).\n\nIn computer science, we translate these real-world actions into precise instructions. We use Sequence to ensure steps happen in the correct order, Selection to allow the program to make decisions based on data, and Iteration to handle repetitive tasks efficiently without writing the same code over and over.
📖 Definitions
🔍 Worked example — Easy
Write pseudocode to input a temperature T. If T > 30, output "Hot", otherwise output "Normal".
🔍 Worked example — Standard
A program inputs 5 numbers and calculates their sum. Write the pseudocode.
🔍 Worked example — Exam-style
An algorithm iterates from x = 1 to x = 10. In each step, if x is even, it adds 5 to a total S. Otherwise, it adds 1 to S. Calculate the final value of S if S starts at 0.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 9.2 (c) Structured English, flowcharts and pseudocode
Structured English describes the steps in plain English, using a restricted set of keywords and indentation:
🧑🏫 Teacher's explanation
Imagine you are explaining to a friend how to bake a cake. If you say, "Mix flour, eggs, and sugar, then bake it," that is too vague. If you say, "Add 200g of flour, 2 eggs, and 100g of sugar, then whisk for 5 minutes," you are using structured English. You are stripping away the color of the bowl or the brand of the oven (abstraction) and focusing only on the steps needed to reach the goal.
📖 Definitions
🔍 Worked example — Easy
Convert the following Structured English into Pseudocode: SET counter to 1 WHILE counter is less than or equal to 5 OUTPUT counter INCREMENT counter by 1 ENDWHILE
🔍 Worked example — Standard
A flowchart contains a decision diamond with the condition 'Score > 50'. If the 'Yes' path leads to a rectangle 'Result <- "Pass"' and the 'No' path leads to a rectangle 'Result <- "Fail"', then both paths join to a terminator 'STOP'. Write the corresponding pseudocode.
🔍 Worked example — Exam-style
An algorithm must calculate the sum of all even numbers from 1 to 20. Write the pseudocode using stepwise refinement principles.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Write the pseudocode for this algorithm. You may assume the list is stored in an array named 'Numbers'. [4 marks]
Key ideas — 9.2 (d) Stepwise refinement
Stepwise refinement is breaking each step of an algorithm into smaller, more detailed steps, repeatedly, until each step is detailed enough to be programmed directly.
🧑🏫 Teacher's explanation
Imagine you are planning a massive music festival. If you just say "Organize the festival," you haven't actually done anything useful. That is too vague to act upon. Instead, you use stepwise refinement: you break "Organize the festival" into "Book bands," "Find a venue," and "Sell tickets." Then, you break "Book bands" into "Contact local bands," "Negotiate fees," and "Sign contracts."
📖 Definitions
🔍 Worked example — Easy
Refine the high-level step: "Calculate the average of three numbers."
🔍 Worked example — Standard
Refine the step: "Check if a user is old enough to vote (18+)."
🔍 Worked example — Exam-style
Refine the high-level instruction: "Find the largest number in a list of n numbers."
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Use stepwise refinement to produce a detailed pseudocode algorithm for this task. [4] [4 marks]
Key ideas — 9.2 (e) Logic statements
A logic statement defines part of an algorithm as a condition using AND, OR and NOT and relational operators. Example: "a customer gets free delivery if they spend more than $50 or are a member, and the item is not oversized":
🧑🏫 Teacher's explanation
Imagine you are a security guard at a club. You have a list of rules to decide who gets in. For example: "You can enter if you are over 18 AND you have a ticket, OR if you are on the VIP list." This single sentence is a logic statement. It takes several individual facts and combines them into one single 'Yes' or 'No' decision.
📖 Definitions
🔍 Worked example — Easy
Evaluate the following logic statement for the given values: \( (A \text{ AND } B) \text{ OR } C \). Values: A = TRUE, B = FALSE, C = TRUE.
🔍 Worked example — Standard
A student passes a course if they score > 50 in the exam AND (score > 40 in the coursework OR score > 40 in the project). Determine if a student with Exam = 55 and Coursework = 35 and Project = 45 passes.
🔍 Worked example — Exam-style
Convert the following logic into a truth table: NOT (P OR Q).
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Worked example
Convert this structured English into pseudocode. "Keep asking for a password until the user enters Secret1 or has had three attempts. Then output either 'Access granted' or 'Locked'."
🔍 Worked example — Easy
Convert this structured English into pseudocode: 'Add two numbers together and output the result.'
🔍 Worked example — Standard
Convert this structured English into pseudocode: 'Repeat a message "Hello" 5 times.'
🔍 Worked example — Exam-style
Convert this structured English into pseudocode: 'Keep asking for a password until the user enters Secret1 or has had three attempts. Then output either "Access granted" or "Locked".'
⚠️ Common errors
Common mistakes
Practice
Answers: (1) To remove unnecessary detail so that only the essential details remain, giving a simpler model; benefit e.g. easier to understand and solve, quicker to program. (2) The problem is split into sub-problems, each a single task; each task can be written as a separate module (procedure/function) that can be developed, tested and reused separately. (3) Count INTEGER loop counter 1–10; Price REAL price of one item; Quantity INTEGER quantity of one item; Total REAL running total cost. (4) Largest ← 0 / INPUT Number / WHILE Number <> 0 / IF Number > Largest THEN Largest ← Number ENDIF / INPUT Number / ENDWHILE / OUTPUT Largest. (5) IF Age >= 14 AND Age <= 16 AND MedicalForm = TRUE THEN ... ENDIF