Fundamentals of algorithms

Overview

Algorithms are the beating heart of Computer Science. At their core, algorithms are simply precise, step-by-step instructions designed to solve specific problems. But mastering this topic is about more than just writing code; it's about developing a computational mindset. This topic introduces you to powerful problem-solving techniques like decomposition and abstraction, and teaches you how to represent your ideas clearly using flowcharts and pseudocode.

Why does this matter? Because before you can write a successful computer program, you need a flawless logical plan. Examiners love testing this topic because it reveals whether you truly understand the logic behind the code. You can expect a mix of questions, from defining key terms to tracing the execution of complex algorithms using trace tables. By mastering these fundamentals, you are building the foundation for the entire programming section of your specification.

Key Concepts

Concept 1: Decomposition

Decomposition is the process of breaking down a large, complex problem into smaller, more manageable sub-problems.

Why does this work? Human brains struggle to hold massive amounts of complexity at once. By dividing a problem, you can tackle each small piece individually. In software development, this allows teams of programmers to work on different parts of a system simultaneously without stepping on each other's toes.

Example: Imagine designing a school management system. That's a huge task! But if you decompose it, you get sub-problems: a system for attendance, a system for grades, a system for timetables, and a system for parent communication. Each of these is easier to design and code than the whole system at once.

Concept 2: Abstraction

Abstraction is the process of removing or hiding unnecessary detail so you can focus on the essential features of a problem.

Why is this necessary? Because real-world problems are often messy and full of irrelevant data. If you tried to model every single physical property of a car in a racing game (like the exact molecular structure of the tires), the game would be too complex to run. Abstraction lets you say: "For this game, I only care about the car's speed, weight, and colour."

Example: The classic example is the London Underground map. It doesn't show the exact geographical twists and turns of the tracks, nor the streets above. It abstracts all that away to show you only what you need to know: the stations and the lines connecting them.

Concept 3: Representing Algorithms (Flowcharts and Pseudocode)

Algorithms are not computer programs. They are the logical plan. To communicate this plan, we use specific representations.

Flowcharts use visual symbols to show the flow of logic:

• Oval/Rounded Rectangle: Start or End (Terminals)
• Rectangle: Process (e.g., count = count + 1)
• Diamond: Decision (e.g., is count > 10?). Crucially, this must have two exits: Yes and No.
• Parallelogram: Input or Output (e.g., OUTPUT count)

Pseudocode is a text-based representation that looks like a simplified programming language. It ignores the strict syntax rules of languages like Python or Java, focusing instead on the logic.

Concept 4: Trace Tables

Trace tables are a manual way to test an algorithm. You create a table with a column for each variable, and you track how the values change step-by-step as you mentally execute the algorithm.

Why do we use them? To find logic errors before we ever write a line of code, or to determine the purpose of an unknown algorithm in an exam.

Example: If an algorithm loops three times, adding 2 to a variable x (which starts at 0) each time, your trace table would show x changing from 0, to 2, to 4, to 6 on successive rows.

Practical Applications

These concepts aren't just for exams; they run the modern world.

• Sat-Navs: Use abstraction (ignoring scenery to focus on roads) and algorithms (finding the shortest path) to get you home.
• Search Engines: Use highly complex algorithms to sort billions of web pages in milliseconds.
• Game Development: Uses decomposition to split work between physics engines, graphics rendering, and AI logic.