What is the difference between Dijkstra and A* algorithm?

Both find the shortest path in a graph, but A* uses a heuristic to estimate the distance to the goal, making it more efficient for large graphs. Dijkstra explores all nodes equally, while A* prioritises nodes that are closer to the goal. A* is commonly used in games and GPS navigation, whereas Dijkstra is used when the exact shortest path is needed without heuristics.

How do I calculate Big O notation for an algorithm?

Identify the basic operation (e.g., comparison, assignment) and count how many times it executes as a function of input size n. Ignore constants and lower-order terms. For loops, multiply the number of iterations. For nested loops, multiply the iterations of each loop. For recursive algorithms, set up a recurrence relation and solve it (e.g., using the Master Theorem).

Why is merge sort O(n log n) and not O(n^2)?

Merge sort divides the array into halves recursively (log n levels) and merges each level in O(n) time. So total time is n * log n. It does not have nested loops that iterate n times each; instead, the divide step reduces the problem size exponentially.

Can I use binary search on a linked list?

Binary search requires random access to elements, which linked lists do not provide. Accessing the middle element of a linked list takes O(n) time, making binary search inefficient. Use linear search instead, or convert the linked list to an array.

What is the worst-case time complexity of quick sort and why?

The worst-case time complexity of quick sort is O(n^2). This occurs when the pivot chosen is always the smallest or largest element, causing the partition to be highly unbalanced (e.g., one subarray of size n-1 and the other of size 0). This can happen if the array is already sorted and the pivot is the first or last element.

How does depth-first search work and when would I use it?

DFS starts at a root node and explores as far as possible along each branch before backtracking. It uses a stack (or recursion). Use DFS when you need to explore all nodes in a graph, detect cycles, or solve puzzles like mazes. It is memory-efficient for deep graphs but can get stuck in infinite loops if cycles are not handled.

Computational methods

OCR

A-Level

This topic focuses on the computational methods used to solve problems, emphasizing the identification of features that make a problem solvable by computational means. It covers key techniques such as problem recognition, decomposition, divide and conquer, and abstraction, alongside advanced methods like backtracking, data mining, heuristics, performance modelling, pipelining, and visualisation.

Objectives

Exam Tips

Pitfalls

Key Terms

Mark Points

Topic Overview

Computational methods is a core topic in OCR A-Level Computer Science that focuses on the mathematical and algorithmic techniques used to solve problems efficiently. It covers a range of methods including binary search, merge sort, quick sort, Dijkstra's shortest path algorithm, A* algorithm, and basic graph traversal algorithms like depth-first and breadth-first search. Understanding these methods is crucial because they form the backbone of efficient programming and are widely used in real-world applications such as route planning, data retrieval, and artificial intelligence.

This topic builds on earlier concepts of algorithms and data structures, extending them to more complex scenarios. You will learn how to analyse the time and space complexity of algorithms using Big O notation, which is essential for comparing algorithm efficiency. Mastery of computational methods allows you to choose the most appropriate algorithm for a given problem, optimise code performance, and understand the trade-offs between different approaches. This knowledge is directly applicable to coursework and exam problems where you must implement or evaluate algorithms.

In the wider subject, computational methods link to topics like data structures (arrays, lists, graphs), recursion, and problem-solving. They also underpin advanced areas such as machine learning, cryptography, and network routing. By the end of this topic, you should be able to trace algorithms, identify their complexity, and apply them to novel situations. This is a high-weight topic in the OCR specification, often appearing in both paper 1 (computer systems) and paper 2 (algorithms and programming).

Key Concepts

Core ideas you must understand for this topic

→Big O notation: Describes the worst-case time complexity of an algorithm, e.g., O(n), O(log n), O(n^2). Understand how to derive it from code or pseudocode.
→Divide and conquer: A strategy used by merge sort and quick sort where a problem is split into smaller subproblems, solved recursively, and combined.
→Graph traversal: Depth-first search (DFS) uses a stack (or recursion) to explore as far as possible along each branch before backtracking; breadth-first search (BFS) uses a queue to explore all neighbours at the current depth first.
→Dijkstra's algorithm: Finds the shortest path from a start node to all other nodes in a weighted graph with non-negative weights. Uses a priority queue to select the node with the smallest tentative distance.
→A* algorithm: An extension of Dijkstra's that uses a heuristic (e.g., Euclidean distance) to estimate the remaining distance, making it more efficient for pathfinding in games and maps.

What You Need to Demonstrate

Key skills and knowledge for this topic

Ability to identify features that make a problem solvable by computational methods
Correct application of problem decomposition and divide and conquer strategies
Effective use of abstraction to simplify complex problems
Application of backtracking, data mining, and heuristics to solve specific problem types
Understanding of performance modelling and pipelining in the context of computational efficiency
Use of visualisation techniques to represent and solve problems

Marking Points

Key points examiners look for in your answers

Ability to identify features that make a problem solvable by computational methods
Correct application of problem decomposition and divide and conquer strategies
Effective use of abstraction to simplify complex problems
Application of backtracking, data mining, and heuristics to solve specific problem types
Understanding of performance modelling and pipelining in the context of computational efficiency
Use of visualisation techniques to represent and solve problems

Examiner Tips

Expert advice for maximising your marks

💡Always justify your choice of computational method with reference to the specific problem constraints
💡When asked about divide and conquer, clearly explain the recursive nature of the process
💡Use clear, concise examples when describing how data mining or heuristics can be applied
💡Ensure you can distinguish between the theoretical model and the practical implementation of an abstraction
💡When tracing algorithms, always show your working. For example, in Dijkstra's, write down the tentative distances and the visited set at each step. This demonstrates understanding and can earn method marks even if the final answer is wrong.
💡For complexity analysis, focus on the dominant term. In nested loops, the innermost operation determines the complexity. Remember that constants and lower-order terms are ignored in Big O.
💡In exam questions that ask you to 'compare' algorithms, mention both time and space complexity, and give a scenario where one is preferable over the other. For example, quick sort is faster on average than merge sort but has worse worst-case performance.

Common Mistakes

Pitfalls to avoid in your exam answers

Confusing abstraction with simple omission of detail
Failing to justify why a problem is amenable to a computational approach
Misapplying heuristics in scenarios where a deterministic algorithm is more appropriate
Neglecting to consider the performance implications of chosen computational methods
Confusing time complexity with actual runtime: Big O describes growth rate, not speed. An O(n^2) algorithm can be faster than an O(n) algorithm for small n due to constant factors.
Thinking that binary search requires a sorted array: Yes, it does. Applying binary search to an unsorted array will produce incorrect results.
Believing that Dijkstra's algorithm works with negative weights: It does not; negative weights can cause infinite loops or incorrect results. Use Bellman-Ford for graphs with negative weights.

Frequently Asked Questions

Common questions students ask about this topic

Before You Start

Prior knowledge that will help with this topic

•Basic understanding of algorithms: what they are and how to represent them using pseudocode or flowcharts.
•Knowledge of data structures: arrays, lists, stacks, queues, and graphs (including adjacency lists and matrices).
•Recursion: how recursive functions work, including base cases and stack frames.

Likely Command Words

How questions on this topic are typically asked

Describe

Explain

Justify

Identify

Apply

Compare

Ready to test yourself?

Practice questions tailored to this topic

Computational methods

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Computer Science

Algorithms

Analysis of the problem

Applications Generation

Boolean Algebra

Topic Synopsis

Key Concepts & Core Principles

Exam Tips & Revision Strategies

Common Misconceptions & Mistakes to Avoid

Examiner Marking Points

Computational methods

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

What is the difference between Dijkstra and A* algorithm?

How do I calculate Big O notation for an algorithm?

Why is merge sort O(n log n) and not O(n^2)?

Can I use binary search on a linked list?

What is the worst-case time complexity of quick sort and why?

How does depth-first search work and when would I use it?

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Computer Science

Algorithms

Analysis of the problem

Applications Generation

Boolean Algebra