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