home
Algorithm Design and Problem-Solving
Algorithms are the core of computer science: step-by-step procedures designed to solve specific problems. This section will introduce the fundamental principles of computational thinking, explore various algorithm design techniques, and guide you through creating clear flowcharts and pseudocode. Master the art of efficient problem-solving for any challenge.
Computational Thinking
Computational thinking is a systematic approach to problem-solving. It involves four key concepts that work together to break down complex problems.
Decomposition
  • Breaking down complex problems into smaller, manageable sub-problems
  • Makes large problems less overwhelming
  • Each sub-problem can be solved independently
  • In programming: Breaking a large program into functions/modules
  • Benefits: Easier to understand, test, and debug
Pattern Recognition
  • Identifying similarities, patterns, and trends in data or problems
  • Recognizing when problems are similar to ones already solved
  • Finding commonalities that can be exploited
  • Helps avoid "reinventing the wheel"
  • Enables use of existing solutions for similar problems
  • Example: Identifying repeated code that can be turned into a function
Abstraction
  • Focusing on important information while ignoring irrelevant details
  • Simplifying problems by removing unnecessary complexity
  • Creating general solutions that work for multiple cases
  • Example: Using a map (abstracts roads, ignores building details)
  • In programming: Variables and classes/objects abstract details
  • Makes problems easier to understand and solve
Algorithm Design
  • Creating step-by-step instructions to solve a problem
  • Must be: Clear, finite, effective, efficient
  • Can be expressed as: Natural language, flowcharts, pseudocode, code
  • Good algorithms are reusable and adaptable
Flowcharts
Flowcharts use standardized symbols to visually represent algorithms. Essential for planning and communicating algorithm logic.
Standard Flowchart Symbols
Terminal (Oval):
  • Start and End points
  • Contains "Start" or "End"
Process (Rectangle):
  • Represents an action or operation
  • Examples: "Add 5 to x"
Decision (Diamond):
  • Yes/No question or condition
  • Two exit paths (True/False)
Input/Output (Parallelogram):
  • Represents data input or output
  • Examples: "Enter name", "Display result"
Flow Lines (Arrows):
  • Shows direction of flow
  • Connects symbols in sequence
Connector (Small Circle):
  • Connects different flowchart parts
  • Useful for large flowcharts
Flowchart Best Practices
  • Flow top to bottom, left to right
  • Clear, concise labels
  • Avoid crossing lines
  • One start, one or more ends
  • Test logic by following paths
Common Flowchart Patterns
Sequence:
  • Steps executed sequentially
Selection (If-Then-Else):
  • If-then-else branches
  • Decision diamond for conditions
Iteration (Loops):
  • Repeating a set of steps
  • Decision to exit loop
When to Use Flowcharts
Advantages:
  • Visual, easy to understand
  • Identifies errors early
  • Language-independent
Limitations:
  • Complex for large algorithms
  • Time-consuming to modify
Pseudocode
Pseudocode uses structured English to plan algorithms before coding. Not tied to any programming language.
1
What is Pseudocode?
  • Informal algorithm description
  • Uses programming-like syntax
  • For planning logic, not execution
2
Common Pseudocode Conventions
Variables and Assignment:
  • SET variable ← value
  • Example: SET count ← 0
Input/Output:
  • INPUT variable
  • OUTPUT message or variable
  • Example: INPUT username, OUTPUT "Hello"
Selection (If statements):
  • IF condition THEN
  • statements
  • ELSE
  • statements
  • ENDIF
Iteration (Loops):
  • WHILE condition DO
  • statements
  • ENDWHILE
  • FOR variable ← start TO end
  • statements
  • ENDFOR
3
Example Pseudocode
Simple example - Find maximum of two numbers:
INPUT num1
INPUT num2
IF num1 > num2 THEN
  OUTPUT num1
ELSE
  OUTPUT num2
ENDIF
4
Benefits
  • Language-independent
  • Focuses on logic not syntax
  • Easy to understand and modify
  • Essential for exams
Searching Algorithms
Searching algorithms find specific data in a collection. Two main types: linear and binary.
Linear Search
How it works: Check each item sequentially until found or end reached
Advantages: Simple, works on unsorted data
Disadvantages: Slow for large datasets
Time: Best O(1), Worst O(n)
Binary Search
How it works: Requires sorted list. Check middle, eliminate half, repeat
Advantages: Much faster for large datasets
Disadvantages: Requires sorted data, more complex
Time: Best O(1), Worst O(log n)
Comparison
Use Linear: Small or unsorted data
Use Binary: Large sorted data
Example: Unsorted class list = linear; Dictionary = binary
Sorting Algorithms
Sorting algorithms arrange data in order. IGCSE focuses on bubble sort - you should understand how it works step-by-step.
Bubble Sort
How:
  • Compare adjacent pairs, swap if wrong order, repeat until sorted
Advantages:
  • Simple, easy to implement
Disadvantages:
  • Slow for large data
Time: O(n²)
Insertion Sort
How:
  • Build sorted list one item at a time, insert each into correct position
Advantages:
  • Simple, good for small/nearly sorted data
Disadvantages:
  • Slow for large data
Time: O(n²)
Merge Sort
How:
  • Divide list in half recursively, sort halves, merge back
Advantages:
  • Fast for large data, consistent performance
Disadvantages:
  • Complex, requires extra memory
Time: O(n log n)
Comparison
  • Small data: Bubble or Insertion
  • Large data: Merge Sort
  • Easiest: Bubble Sort
  • Most efficient: Merge Sort
Validation and Verification
When data is entered into a computer system, it's crucial to ensure it's accurate and appropriate. Two key processes help achieve this: validation and verification. While they sound similar, they serve different purposes in maintaining data quality.
Validation
Validation checks that data meets certain rules and is reasonable, sensible, and within acceptable boundaries. It's performed automatically by the computer.
Types of Validation Checks:
  • Range Check: Ensures data falls within a specified range (e.g., age between 0-120)
  • Length Check: Verifies data has the correct number of characters (e.g., phone number must be 11 digits)
  • Type Check: Confirms data is the correct data type (e.g., number not text in age field)
  • Presence Check: Ensures required fields are not left empty
  • Format Check: Checks data follows a specific pattern (e.g., email must contain @)
  • Check Digit: Uses a calculation to verify accuracy (e.g., ISBN, barcode numbers)
Verification
Verification checks that data has been accurately copied or transferred from one source to another. It ensures data entered matches the original source.
Types of Verification Checks:
  • Visual Check: A person visually compares the entered data with the original source to spot errors
  • Double Entry Check: Data is entered twice (by same or different people) and the computer compares both entries to ensure they match
Key Difference:
Validation asks: "Is this data reasonable and within rules?"
Verification asks: "Is this data exactly what was intended?"
Example: Entering a date of birth as 31/02/2005 would pass verification (if typed correctly twice) but fail validation (February doesn't have 31 days).
Test Data
Testing is essential to ensure programs work correctly. Test data is deliberately chosen input values used to check if a program functions as expected. Different types of test data help identify different kinds of errors.
Normal Data
  • Data that is valid and within expected boundaries
  • Should be accepted and processed correctly by the program
  • Example: If a program accepts ages 11-18, test with 14, 16
  • Purpose: Confirms the program works under typical conditions
Abnormal Data
  • Data that is invalid and should be rejected
  • Completely outside acceptable values or wrong data type
  • Example: If a program accepts ages 11-18, test with -5, 150, "hello"
  • Purpose: Checks the program handles invalid input gracefully with appropriate error messages
Extreme Data
  • Data at the very limits of what is acceptable
  • The largest or smallest values that should still be accepted
  • Example: If a program accepts ages 11-18, test with 11 and 18
  • Purpose: Verifies the program correctly accepts boundary values
Boundary Data
  • Tests both sides of a boundary (valid and invalid)
  • Includes the extreme values AND the values just outside them
  • Example: If a program accepts ages 11-18, test with 10, 11, 18, 19
  • Purpose: Most thorough test - catches off-by-one errors
Why Boundary Testing is Critical:
Boundary data is the most important test type because errors often occur at the edges of acceptable ranges. A program might work perfectly for normal data but fail at boundaries due to incorrect use of comparison operators (< vs ≤).
Example Test Plan for "Enter a percentage (0-100)":
  • Normal: 50, 75
  • Extreme: 0, 100
  • Boundary: -1, 0, 100, 101
  • Abnormal: -50, 200, "fifty"
Trace Tables
A trace table is a technique used to test and debug algorithms by manually tracking the values of variables as each step of the algorithm executes. This process, called a "dry run," helps identify logic errors before writing actual code.
What is a Trace Table?
A trace table is a structured table where:
  • Each column represents a variable or output
  • Each row represents a step in the algorithm's execution
  • Values are recorded as they change throughout the algorithm
Why Use Trace Tables?
Identify logic errors in algorithms before coding
Understand how an algorithm works step-by-step
Verify that an algorithm produces expected results
Essential exam skill for IGCSE Computer Science
Example Algorithm:
Total ← 0
Counter ← 1
REPEAT
    Total ← Total + Counter
    Counter ← Counter + 1
UNTIL Counter > 3
OUTPUT Total
Trace Table:
How to Complete a Trace Table:
  1. Create columns for each variable and any outputs
  1. Work through the algorithm line by line
  1. Record the value of variables after each change
  1. Only fill in cells when values change
  1. Record outputs when OUTPUT statements execute
  1. Continue until the algorithm terminates
Common Exam Tips:
  • Leave cells blank if a variable hasn't changed
  • Show all intermediate steps, not just final values
  • Include a column for outputs/user prompts if needed
  • Check your final values match expected results
  • Use trace tables to spot infinite loops or incorrect conditions
Identifying and Correcting Algorithm Errors
Even experienced programmers make mistakes. The ability to identify errors in algorithms and suggest corrections is a crucial skill. Understanding common error types helps you debug more effectively and write better code from the start.
Three Common Types of Errors:
Syntax Errors
  • Mistakes in the structure or grammar of the code
  • Examples: Missing brackets, incorrect keywords, typos in variable names
  • Usually caught by compilers/interpreters
  • Example: Writing "OUPUT" instead of "OUTPUT"
  • Fix: Correct the spelling or structure
Logic Errors
  • Code runs without crashing but produces incorrect results
  • Most difficult to find because the program appears to work
  • Examples: Wrong operator (+ instead of -), incorrect loop condition, wrong formula
  • Example: Using Counter < 10 when you meant Counter <= 10
  • Fix: Use trace tables to track variable values and identify where logic fails
Runtime Errors
  • Errors that occur during program execution
  • Examples: Division by zero, accessing array out of bounds, infinite loops
  • Program may crash or hang
  • Example: WHILE Counter > 0 DO Counter ← Counter + 1 (infinite loop)
  • Fix: Add proper validation and boundary checks
Common Algorithm Errors to Watch For:
Incorrect Loop Conditions:
  • Using < instead of <= (or vice versa)
  • Wrong starting or ending values
  • Infinite loops due to condition never becoming false
Variable Issues:
  • Using variables before initializing them
  • Not updating counter variables in loops
  • Confusing similar variable names
Operator Mistakes:
  • Using = (assignment) instead of == (comparison)
  • Wrong arithmetic operators
  • Incorrect order of operations
Off-by-One Errors:
  • Arrays starting at 0 or 1 (depending on language)
  • Loop running one time too many or too few
  • Boundary conditions incorrect
Exam Strategy:
When asked to identify errors:
  1. Read the algorithm carefully and understand its purpose
  1. Use a trace table to track variable values
  1. Check loop conditions and boundaries
  1. Verify variable initialization
  1. Test with normal, extreme, and boundary data
  1. Suggest specific corrections with clear explanations
Powered by Bytonix — Digital Learning for Computer Science