Fundamentals of algorithms — AQA A-Level Computer Science

Fundamentals of algorithms is the bedrock of computer science, covering the design, analysis, and implementation of step-by-step procedures to solve problems. This topic introduces you to key concepts such as algorithmic thinking, decomposition, abstraction, and the use of standard algorithms like searching and sorting. Mastering these fundamentals is essential because algorithms are at the heart of every software system, from simple calculators to complex AI. In the AQA A-Level, you'll learn to write algorithms in pseudocode and flowcharts, analyse their efficiency, and apply them to real-world scenarios.

Understanding algorithms is not just about memorising steps; it's about developing a logical mindset that allows you to break down problems into manageable parts. This topic connects directly to data structures, programming, and computational thinking. For example, knowing how a binary search works helps you understand why certain data structures (like sorted arrays) are efficient. In exams, you'll be expected to trace algorithms, identify errors, and compare their performance using Big O notation. This foundational knowledge is crucial for higher-level topics like graph algorithms and recursion.

Algorithms are everywhere: from Google's search engine to Netflix's recommendation system. By studying this topic, you'll gain the skills to create efficient solutions and appreciate the trade-offs between time and space complexity. The AQA specification emphasises practical application, so you'll often be asked to implement algorithms in a programming language or pseudocode. This topic also lays the groundwork for the non-exam assessment (NEA), where you'll design and evaluate your own algorithms to solve a problem of your choice.

• →Algorithmic thinking: The ability to break down problems into clear, logical steps and represent them as algorithms using pseudocode or flowcharts.
• →Searching algorithms: Linear search (O(n)) and binary search (O(log n)) – understand their steps, efficiency, and when to use each (binary search requires sorted data).
• →Sorting algorithms: Bubble sort (O(n^2)), merge sort (O(n log n)), and insertion sort (O(n^2)) – know how they work, their best/worst-case complexities, and stability.
• →Big O notation: A way to describe the time and space complexity of an algorithm, focusing on the worst-case scenario. For example, O(1) is constant time, O(n) is linear, O(n^2) is quadratic.
• →Trace tables: A method to manually execute an algorithm step by step, recording variable values to verify correctness or find errors.

• Ability to trace breadth-first and depth-first search algorithms
• Ability to trace pre-order, post-order, and in-order tree-traversal algorithms
• Ability to convert between infix and Reverse Polish notation
• Knowledge of time complexity for linear search, binary search, and binary tree search
• Knowledge of time complexity for bubble sort and merge sort
• Ability to trace Dijkstra’s shortest path algorithm
• Understanding of Big-O notation for constant, logarithmic, linear, polynomial, and exponential time
• Understanding of the Halting problem and its significance

• 💡Practice tracing algorithms manually on paper to ensure accuracy
• 💡Memorize the time complexity classes (O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n))
• 💡Use clear, step-by-step notation when converting to RPN
• 💡Ensure you can explain the 'Divide and Conquer' approach used in merge sort
• 💡Be prepared to explain the significance of the Halting problem as a limit of computation
• 💡When tracing algorithms, always use a trace table and update variables systematically. Examiners look for clear, step-by-step working – even if your final answer is wrong, you can get marks for correct intermediate steps.
• 💡For algorithm design questions, start by writing the steps in plain English (pseudocode) before translating into a specific programming language. This shows your understanding of the logic and helps avoid syntax errors.
• 💡When comparing algorithms, always refer to Big O notation and justify your answer with specific examples (e.g., 'Binary search is faster than linear search for large sorted datasets because it halves the search space each iteration, giving O(log n) vs O(n)').

• Confusing the order of traversal in tree algorithms (e.g., pre-order vs post-order)
• Incorrectly calculating time complexity for algorithms
• Failing to correctly convert infix expressions to RPN
• Misunderstanding the difference between tractable and intractable problems
• Inability to correctly trace Dijkstra's algorithm steps
• Misconception: Binary search can be used on any list. Correction: Binary search only works on sorted data. If the list is unsorted, you must sort it first or use linear search.
• Misconception: Merge sort always takes the same amount of time. Correction: Merge sort has a consistent O(n log n) time complexity regardless of input order, but it requires additional memory for merging, so it's not always the best choice for small datasets.
• Misconception: Bubble sort is the slowest sorting algorithm. Correction: While bubble sort is generally inefficient (O(n^2)), it can be optimised to stop early if no swaps occur, making it O(n) on an already sorted list. However, insertion sort often performs better in practice.