Understand standard methods of solution

Algorithm Design & Problem‑Solving

What is an Algorithm?

An algorithm is a step‑by‑step recipe that tells a computer how to solve a problem. Think of it like a cooking recipe: you need a list of ingredients (data), a set of instructions (operations), and a clear end result (output).

Why Algorithms Matter in IGCSE CS?

Algorithms help you:

  • Break a complex problem into manageable parts.
  • Write clear, efficient code.
  • Predict how long a program will run (time complexity).
  • Show evidence of logical thinking in exams.

Standard Methods of Solution

  1. Brute Force – Try every possible solution. Good for small inputs but slow for large ones.

    Example: To find the largest number in a list, compare each number with every other number.

  2. Divide and Conquer – Split the problem into sub‑problems, solve each, then combine results.

    Example: Merge Sort – split the list, sort each half, then merge.

  3. Greedy Algorithms – Make the best local choice at each step.

    Example: Coin change – always pick the largest coin that does not exceed the remaining amount.

  4. Dynamic Programming – Store results of sub‑problems to avoid recomputation.

    Example: Fibonacci numbers – keep a table of previously calculated values.

  5. Backtracking – Explore all possibilities, undoing choices when they lead to dead ends.

    Example: Solving a Sudoku puzzle.

Algorithm Analysis

We measure how fast an algorithm runs using time complexity and how much memory it uses with space complexity. The most common notation is Big‑O.

Complexity Example
O(1) – Constant time Accessing an array element by index.
O(n) – Linear time Finding the maximum in a list.
O(n²) – Quadratic time Bubble sort.
O(log n) – Logarithmic time Binary search.

Remember: faster is not always better – sometimes a slightly slower algorithm is easier to understand and less error‑prone.

Exam Tip Box

  • Always state the algorithm’s time complexity in your answer.
  • Use pseudocode to show your thought process.
  • Explain why you chose a particular method (e.g., greedy vs. dynamic programming).
  • Check for edge cases – e.g., empty list, single element.
  • Remember the Big‑O notation rules: drop constants and lower‑order terms.

Practical Example: Sorting Numbers

Let’s design a simple selection sort algorithm.

  1. Start at the first element.
  2. Find the smallest element in the unsorted portion.
  3. Swap it with the current position.
  4. Move to the next position and repeat until the list is sorted.

Time complexity: $O(n^2)$, Space complexity: $O(1)$.

Quick Quiz

Which algorithm would you use to find the shortest path in a weighted graph?

  • A) Brute Force
  • B) Greedy (Dijkstra’s)
  • C) Backtracking

Answer: B) Greedy (Dijkstra’s). It always picks the nearest unvisited node, ensuring the shortest path is found efficiently.

Key Takeaways

  • Algorithms are recipes that solve problems step by step.
  • Choose the right method (brute force, divide & conquer, greedy, DP, backtracking) based on the problem size and constraints.
  • Always analyse time and space complexity.
  • Use pseudocode and clear explanations in exams.
  • Practice by solving a variety of problems – the more you practice, the better you become at recognising patterns.

Revision

Log in to practice.

3 views 0 suggestions