Cambridge O Level2210

Algorithm design and problem-solving

Computer Science 2210 Chapter Notes

What this chapter covers

Algorithm design and problem-solving
ShareWhatsAppPost
Algorithm design and problem-solving notes

Unable to load PDF

The notes viewer could not load. Please refresh the page.

Read online free. Download a watermarked copy with a free account.

Read the notes

The full Algorithm design and problem-solving notes as text: skim, search, and jump between subtopics.

~15 min read

In this chapter

  1. 1The Program Development Life Cycle
  2. 2Decomposition and Structure Diagrams
  3. 3Designing Algorithms: Pseudocode and Flowcharts
  4. 4Linear Search and Bubble Sort
  5. 5Finding Maximum, Minimum, and Average
  6. 6Data Validation and Verification
  7. 7Testing, Tracing, and Debugging

1. The Program Development Life Cycle

Creating software is a structured process, not a single event. The Program Development Life Cycle (PDLC) is a framework that outlines the key stages a project goes through from concept to completion and beyond. Following these stages helps to ensure the final program is well-designed, functional, and meets the user's needs. The process is often iterative, meaning developers might circle back to earlier stages as the project evolves or if issues are discovered.

Key term

Program Development Life Cycle: The structured, multi-stage process used to design, develop, and maintain a software system.

Examiner insight

Examiners often ask for descriptions of stages beyond just naming them, so be prepared to explain what happens in each one and what the outcome is.

Worked example 14 marks

One stage of the program development life cycle is the analysis. Identify and describe two other stages. [4]

  1. 1

    Stage 1: Design. In this stage, the requirements from the analysis are used to plan the solution. This involves creating algorithms (using pseudocode or flowcharts), planning data structures, and designing the user interface.

  2. 2

    Stage 2: Testing. In this stage, the completed code is rigorously tested to find and fix errors. This involves running the program with different sets of test data (normal, boundary, erroneous) to ensure it works as expected and is robust.

Recap

  • The PDLC provides a structured approach to software creation.
  • The 'Analysis' stage is about understanding and defining the problem and user requirements.
  • The 'Design' stage involves planning the solution using tools like flowcharts and pseudocode.
  • The 'Coding' stage is where the program is written in a programming language.
  • The 'Testing' stage is crucial for finding and fixing errors before release.
  • The 'Maintenance' stage involves updating and supporting the program after it has been deployed.

Quick check

  1. Name the five main stages of the Program Development Life Cycle.2 marks

2. Decomposition and Structure Diagrams

Complex problems are difficult to solve all at once. Decomposition is the technique of breaking down a large, complex problem into smaller, more manageable sub-problems. Each sub-problem can then be solved independently, and sometimes even broken down further. A structure diagram is a visual tool used to show this process. It's a hierarchical chart that illustrates how a main system is divided into its constituent sub-systems or modules. This 'top-down' approach makes the overall problem much easier to understand, design, and manage, especially when working in a team.

Key term

Decomposition: The process of breaking down a complex problem or system into smaller, more manageable parts.

Fun fact

The 'divide and conquer' strategy used in decomposition is a fundamental principle not just in computer science, but also in engineering, business management, and military strategy.

Worked example 14 marks

A school wants a system to manage student attendance. The main functions are to record daily attendance, generate absence reports for parents, and produce a weekly summary for the head teacher. Draw a structure diagram to show the decomposition of this system. [4]

  1. 1

    Start with the main system at the top: 'Student Attendance System'.

  2. 2

    Break this down into the three main functions identified. Create a second level of boxes connected to the top box: 'Record Attendance', 'Generate Reports', 'Weekly Summary'.

  3. 3

    Consider if any of these can be broken down further. The 'Generate Reports' module could be split into 'Parent Absence Report' and 'Student-Specific Report'.

  4. 4

    The final diagram should show 'Student Attendance System' at the top, branching down to 'Record Attendance', 'Generate Reports', and 'Weekly Summary'. 'Generate Reports' then branches further down to its two sub-reports.

Recap

  • Decomposition simplifies complex problems by breaking them down.
  • It allows for a 'top-down' design approach.
  • Structure diagrams are used to visually represent the decomposition of a system.
  • These diagrams show the hierarchy of modules and sub-systems.
  • Decomposition makes it easier to allocate tasks to different members of a programming team.

Quick check

  1. What is the purpose of a structure diagram?1 mark

3. Designing Algorithms: Pseudocode and Flowcharts

Before writing a single line of code, a programmer must design the algorithm's logic. Two standard tools for this are pseudocode and flowcharts. A flowchart is a diagram that uses standard symbols to represent the different actions and decisions in an algorithm. It visually shows the 'flow' of control. Pseudocode, on the other hand, uses structured English-like statements to describe the steps. It is not a real programming language, so it cannot be compiled, but it uses keywords (like IF, THEN, ELSE, FOR, WHILE, INPUT, OUTPUT) that make it easy to convert into actual code later. Both tools help programmers to think through the logic without worrying about the strict syntax of a specific language.

Key term

Pseudocode: A plain language description of the steps in an algorithm, using structured English and keywords but not tied to a specific programming language.

Common pitfall

Confusing the flowchart symbols, especially using the process rectangle for inputs or outputs. Remember, I/O always uses a parallelogram.

Worked example 13 marks

Write pseudocode for an algorithm that asks the user to enter a password. If the password is 'secret123', it should output 'Access granted'. Otherwise, it should output 'Access denied'. [3]

  1. 1

    Step 1 (Input): First, the program needs to get the password from the user. `OUTPUT "Enter password:"` followed by `INPUT UserPassword`

  2. 2

    Step 2 (Process/Decision): Next, it must compare the user's input to the correct password. `IF UserPassword == "secret123" THEN`

  3. 3

    Step 3 (Outputs): Based on the comparison, output the correct message. `OUTPUT "Access granted"` `ELSE` `OUTPUT "Access denied"` `ENDIF`

Worked example 24 marks

Draw a flowchart for the password algorithm described in the previous example. [4]

  1. 1

    Start with a 'Start' terminator symbol (oval).

  2. 2

    Add an arrow to an 'Output "Enter password:"' parallelogram.

  3. 3

    Add an arrow to an 'Input UserPassword' parallelogram.

  4. 4

    Add an arrow to a 'UserPassword == "secret123"?' decision diamond.

  5. 5

    From the 'Yes' branch of the diamond, draw an arrow to an 'Output "Access granted"' parallelogram.

  6. 6

    From the 'No' branch of the diamond, draw an arrow to an 'Output "Access denied"' parallelogram.

  7. 7

    Draw arrows from both output parallelograms to a single 'End' terminator symbol (oval).

Recap

  • Flowcharts visually represent an algorithm's logic using standard symbols.
  • Pseudocode describes an algorithm's logic using structured, English-like statements.
  • Both are created during the 'Design' phase of the PDLC.
  • Key flowchart symbols: Oval (Start/End), Parallelogram (Input/Output), Rectangle (Process), Diamond (Decision).
  • Key pseudocode keywords: INPUT, OUTPUT, IF/THEN/ELSE, WHILE/ENDWHILE, FOR/NEXT.

Quick check

  1. In a flowchart, what shape is used to represent a decision?1 mark
  2. Is pseudocode a programming language?1 mark

4. Linear Search and Bubble Sort

Searching and sorting are two of the most common tasks a computer performs. A Linear Search is the simplest way to find an item in a list. It starts at the beginning of the list and checks each item one by one until it either finds the target value or reaches the end of the list. A Bubble Sort is a simple algorithm for arranging a list into order (e.g., ascending). It works by repeatedly stepping through the list, comparing adjacent items, and swapping them if they are in the wrong order. This process is repeated in 'passes' until no more swaps are needed, meaning the list is sorted.

Key term

Bubble Sort: A simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order.

Examiner insight

For bubble sort questions, you must show the state of the list after each complete pass. Simply writing the final sorted list will not earn full marks.

Fun fact

While simple to understand, bubble sort is very inefficient for large lists. Sorting a million items with bubble sort could take days, while more advanced algorithms like Quicksort could do it in seconds.

Worked example 14 marks

Show the passes of a bubble sort to arrange the list `[7, 4, 2, 9]` into ascending order. [4]

  1. 1

    Initial List: `[7, 4, 2, 9]`

  2. 2

    Pass 1: Compare 7 and 4 (swap) -> `[4, 7, 2, 9]`. Compare 7 and 2 (swap) -> `[4, 2, 7, 9]`. Compare 7 and 9 (no swap). End of Pass 1: `[4, 2, 7, 9]`

  3. 3

    Pass 2: Compare 4 and 2 (swap) -> `[2, 4, 7, 9]`. Compare 4 and 7 (no swap). Compare 7 and 9 (no swap). End of Pass 2: `[2, 4, 7, 9]`

  4. 4

    Pass 3: Compare 2 and 4 (no swap). Compare 4 and 7 (no swap). Compare 7 and 9 (no swap). No swaps were made, so the list is sorted. Final List: `[2, 4, 7, 9]`

Worked example 22 marks

Perform a linear search to find the number `2` in the list `[7, 4, 2, 9]`. Describe the steps. [2]

  1. 1

    Step 1: Compare the target `2` with the first item `7`. They do not match.

  2. 2

    Step 2: Compare the target `2` with the second item `4`. They do not match.

  3. 3

    Step 3: Compare the target `2` with the third item `2`. They match. The item is found at index 2 (or position 3).

Recap

  • A linear search checks every element in a list sequentially until a match is found or the list ends.
  • Linear search can be used on both sorted and unsorted lists.
  • A bubble sort arranges a list by repeatedly comparing and swapping adjacent elements.
  • Bubble sort requires multiple passes to sort a list completely.
  • The largest (or smallest) value 'bubbles' to its correct position in each pass of a bubble sort.

Quick check

  1. What is the maximum number of comparisons needed for a linear search on a list of 100 items?1 mark

5. Finding Maximum, Minimum, and Average

Many programs need to process lists of numbers to find key statistics. Three fundamental tasks are finding the maximum value, the minimum value, and the average. The logic for finding the maximum is to create a variable (e.g., `MaxVal`) and initialise it to the first value in the list. Then, loop through the rest of the list, and if any item is greater than `MaxVal`, update `MaxVal` to that item's value. The logic for finding the minimum is identical, but you check if an item is *less than* the current minimum. To find the average, you must first calculate the sum of all numbers and count how many numbers there are. The average is then the total sum divided by the count.

Average = TotalSum / NumberOfItems

Key term

Algorithm: A finite sequence of well-defined, computer-implementable instructions to solve a class of problems or to perform a computation.

Common pitfall

When finding the maximum, incorrectly initializing the `MaxNum` variable to 0. If all input numbers are negative, the algorithm will fail and incorrectly output 0.

Worked example 15 marks

Write a pseudocode algorithm that will input five numbers and output the largest number entered. [5]

  1. 1
    1. Initialize a variable to hold the maximum. To be safe, set it to a very low number or the first input. `INPUT FirstNum` `MaxNum <- FirstNum`
  2. 2
    1. Set up a loop to run for the remaining four numbers. `FOR Counter <- 1 TO 4`
  3. 3
    1. Inside the loop, get the next number. `INPUT NextNum`
  4. 4
    1. Compare the new number with the current maximum. `IF NextNum > MaxNum THEN`
  5. 5
    1. If the new number is larger, update the maximum. `MaxNum <- NextNum` `ENDIF`
  6. 6
    1. After the loop, the maximum number is found. `NEXT Counter` `OUTPUT "The largest number is ", MaxNum`

Recap

  • To find the maximum, initialize a variable to the first value and update it if a larger value is found.
  • To find the minimum, initialize a variable to the first value and update it if a smaller value is found.
  • To calculate an average, you need to find the total sum and the count of items first.
  • These algorithms all rely on iterating through a list of values using a loop.
  • The initialization step is critical for these algorithms to work correctly.

Quick check

  1. To find the average of 20 numbers, what two values must you track inside your loop?2 marks

6. Data Validation and Verification

Ensuring data is correct is vital for any computer system. Validation and verification are two different techniques used to achieve this. Validation is an automatic check performed by the program to ensure that the data being entered is sensible, reasonable, and acceptable. For example, checking that an age entered is between 0 and 120. The program doesn't know if the age is *true*, only if it's a *possible* age. Verification, on the other hand, is a check to ensure that data has been transcribed correctly from one source to another. It's about preventing entry errors. A common example is asking a user to enter their password twice; the system verifies that the two entries match.

Key term

Validation: An automatic check performed by a computer to ensure that data is sensible and reasonable before it is processed.

Examiner insight

Examiners reward answers that give a specific example of a validation check (e.g., 'a range check to ensure age is between 18 and 99') rather than just saying 'a range check'.

Fun fact

The 'CAPTCHA' tests (e.g., 'select all images with a bicycle') you see online are an advanced form of validation, designed to check that the user is a human and not a bot.

Worked example 14 marks

A website has a form for booking a hotel room. The user must enter their email address and the number of nights they wish to stay (1-14). Describe one validation check and one verification method that could be used. [4]

  1. 1

    Validation Check: A range check on the number of nights. The program would check that the number entered is greater than or equal to 1 AND less than or equal to 14. If it is outside this range, an error message would be displayed.

  2. 2

    Verification Method: Double entry for the email address. The form could have two fields, 'Email Address' and 'Confirm Email Address'. The system would only accept the data if the text entered into both fields is identical, reducing the chance of a typing error.

Recap

  • Validation checks if data is reasonable and sensible.
  • Verification checks if data has been entered accurately.
  • Examples of validation: range check, type check, format check, presence check.
  • Examples of verification: double entry, visual check (proofreading).
  • Validation is automated by the computer; verification often involves the user.

Quick check

  1. Is checking that a postcode has the correct structure (e.g., SW1A 0AA) an example of validation or verification?1 mark

7. Testing, Tracing, and Debugging

No program is perfect on the first try. Testing is the process of finding errors (bugs) in a program. To test effectively, we use different types of test data. Normal data is sensible, expected input. Boundary data is input at the very edges of what is acceptable (e.g., if a valid range is 1-10, boundary data would be 1 and 10). Erroneous data is invalid input that the program should reject. When an error is found, we need to locate it. A trace table is a powerful tool for this. It's a table that you fill in by hand, tracking the value of each variable as you manually step through the algorithm's logic. This helps you compare what the algorithm is actually doing with what it should be doing, allowing you to pinpoint the source of a logic error. The process of finding and fixing these errors is called debugging.

Key term

Trace Table: A table used to manually test the logic of an algorithm by tracking variable values as the program executes step-by-step.

Examiner insight

Marks are awarded for correctly setting up the trace table with columns for each variable and for methodically updating values line by line as the algorithm executes.

Common pitfall

When completing a trace table, students sometimes jump ahead or calculate the final value in their head instead of showing how each variable changes at each step of the loop.

Worked example 13 marks

An algorithm is supposed to accept a percentage mark from 0 to 100 inclusive. Identify one piece of normal, one piece of boundary, and one piece of erroneous test data. [3]

  1. 1

    Normal Data: Any typical value, e.g., 75.

  2. 2

    Boundary Data: A value at the edge of the valid range, e.g., 0 or 100.

  3. 3

    Erroneous Data: A value that should be rejected, e.g., 101 or -5 or 'abc'.

Worked example 25 marks

Complete a trace table for the following algorithm when the input is 4. What is the final output? [5]

`INPUT Num Total <- 0 WHILE Num > 0 DO Total <- Total + Num Num <- Num - 1 ENDWHILE OUTPUT Total`

  1. 1

    Set up the table with columns: `Num`, `Total`, `Condition: Num > 0`, `Output`.

  2. 2

    Initial state: `Num` is 4, `Total` is 0.

  3. 3

    Loop 1: `Num > 0` is true. `Total` becomes 0 + 4 = 4. `Num` becomes 4 - 1 = 3.

  4. 4

    Loop 2: `Num > 0` is true. `Total` becomes 4 + 3 = 7. `Num` becomes 3 - 1 = 2.

  5. 5

    Loop 3: `Num > 0` is true. `Total` becomes 7 + 2 = 9. `Num` becomes 2 - 1 = 1.

  6. 6

    Loop 4: `Num > 0` is true. `Total` becomes 9 + 1 = 10. `Num` becomes 1 - 1 = 0.

  7. 7

    Loop 5: `Num > 0` is false. The loop terminates.

  8. 8

    Final step: `OUTPUT Total`. The value 10 is output.

Recap

  • Testing is essential to find bugs in a program.
  • Use normal, boundary, and erroneous data for thorough testing.
  • A trace table is used to manually execute an algorithm and track variable values.
  • Trace tables are excellent for finding logic errors.
  • Debugging is the process of identifying and correcting errors in code.

Quick check

  1. For a check that accepts numbers from 50 to 100, what are the two boundary test data values?2 marks

End-of-chapter exercise

Test yourself on the whole chapter. Work through these before moving on.

  1. Define the terms 'algorithm' and 'pseudocode'.2 marks
  2. Describe two stages of the Program Development Life Cycle, other than 'Coding'.4 marks
  3. A program needs to take a student's percentage mark (an integer from 0 to 100) and output a grade. Describe three different types of test data you would use for this program, giving a specific example for each.6 marks
  4. Draw a flowchart for an algorithm that asks a user for their age and outputs 'Child' if they are under 18, and 'Adult' if they are 18 or over.5 marks
  5. The following is a list of numbers: `[12, 5, 22, 8, 17]`. Show the state of the list after each pass of a bubble sort algorithm sorting into ascending order.5 marks
  6. Explain the difference between validation and verification, using an example for each related to booking a flight online.4 marks
  7. Write a pseudocode algorithm that allows a user to enter 10 positive numbers, then calculates and outputs the smallest number entered.5 marks
  8. A system for a cinema booking is being designed. The system needs to allow users to search for films, select seats, make payments, and receive tickets. Create a structure diagram to show the decomposition of this system into at least four sub-systems.4 marks
  9. Complete the trace table below for the given pseudocode algorithm when the user inputs the value `5`. `INPUT N Total <- 1 Count <- 1 WHILE Count <= N DO Total <- Total * Count Count <- Count + 1 ENDWHILE OUTPUT Total` | N | Total | Count | Condition: Count <= N | Output | |---|---|---|---|---| | | | | | |6 marks
  10. Describe the purpose of the algorithm in Question 9.2 marks

Go deeper

Practise and revise with member-only material for this chapter.

Workbook

Exam-style practice questions with full worked solutions.

Unlock with a plan

Chapter at a Glance

A single-page summary of every key idea for fast revision.

Unlock with a plan

Free notes are just the start.

Unlock every Workbook and Chapter at a Glance, and generate your own worksheets and predicted papers.

Explore plans

Related chapters

Number systemsTypes and methods of data transmissionComputer architectureTypes of software and interruptsThe internet and the world wide webAutomated systems