Algorithms

What Algorithms covers

Algorithms is examined on component 02 of OCR Computer Science, Algorithms and programming. 230 recall questions across 17 subtopics.

The 17 subtopics

Each one has its own page.

• Designing and analysing an algorithmRecall questions on what an algorithm is, analysing a problem before designing, decomposition, pre-conditions and post-conditions, expressing designs, trace tables, off-by-one and boundary testing, iterative versus recursive designs, choosing data structures and generality.Open →
• Measuring efficiency and Big O notationRecall questions on why timing is a poor measure, Big O notation, time and space complexity, constant, logarithmic, linear, polynomial and exponential complexity, estimating run times, ordering complexities, best, average and worst cases, and sorting in place.Open →
• Comparing algorithms and choosing one for a taskRecall questions on choosing between algorithms by complexity, why constants can let a slower-growing algorithm lose, hybrid sorts, memory and data size, sorting on embedded devices and servers, sorted versus unsorted searching, and Dijkstra's versus A*.Open →
• StacksRecall questions on stacks and LIFO, push and pop algorithms, the complexity of push, pop and peek, tracing stack operations, overflow and underflow, static and dynamic stacks, subroutine returns, reversing words and bracket matching.Open →
• QueuesRecall questions on queues and FIFO, adding and removing items, linear and circular queues, tracing a circular queue, telling full from empty, priority queues, breadth-first traversal, keyboard buffers, and the complexity of queue operations.Open →
• Linked listsRecall questions on how linked lists are stored, traversal, inserting into and deleting from an ordered list, tracing an array-based list, the free space list, linked lists versus arrays, binary search on a linked list, and time complexity.Open →
• Trees and binary search treesRecall questions on rooted trees and their terms, the binary search tree rule, adding values, how insertion order changes search cost, searching with comparison counts, time complexity, finding the smallest value, uses of trees and expression trees.Open →
• Traversing a tree: depth-first and breadth-firstRecall questions on depth-first and breadth-first traversals, pre-order, in-order and post-order rules and their uses, tracing each on a binary search tree, reverse Polish from an expression tree, memory use, and time complexity.Open →
• Bubble sortRecall questions on how bubble sort works and why it is named so, tracing passes, shortening passes, the swap flag optimisation, best, average and worst-case and space complexity, comparison counts, and why it is slower than insertion sort.Open →
• Insertion sortRecall questions on how insertion sort works, tracing it, the sorted section invariant, best, worst and average-case and space complexity, nearly sorted and arriving data, comparison with bubble sort, stability, and when to choose it.Open →
• Merge sortRecall questions on the divide and merge phases of merge sort, merging two sorted lists, tracing a merge sort, why it is O(n log n) in every case, levels of splitting, space complexity, stability, external sorting, and when to choose it.Open →
• Quick sortRecall questions on how quick sort works, pivots and partitioning, tracing a quick sort, best, average and worst-case complexity, choosing pivots to avoid the worst case, space complexity, recursion depth, and comparing quick sort with merge sort.Open →
• Comparing the four sorting algorithmsRecall questions on the time and space complexity of bubble, insertion, merge and quick sort, which are stable, how each handles sorted and reversed data, and ranking the four sorts for small and very large lists.Open →
• Linear searchRecall questions on the linear search algorithm, tracing successful and unsuccessful searches, best, average and worst-case and space complexity, unsorted data and linked lists, when linear search is the right choice, and checking for the end.Open →
• Binary searchRecall questions on the binary search algorithm and its sorted-data precondition, tracing successful and unsuccessful searches, best and worst-case and space complexity, maximum comparisons, sorting before searching, and moving pointers past the middle.Open →
• Dijkstra's shortest path algorithmRecall questions on what Dijkstra's shortest path algorithm solves, weighted graphs, the distance table and repeating step, a worked example, recovering the route, negative weights, unreachable nodes, time complexity, uses, and provisional versus final distances.Open →
• The A* algorithmRecall questions on the A* algorithm and its relation to Dijkstra's, heuristics and g, h and f values, admissible heuristics, a worked A* search, checking admissibility, what the heuristic gains, poor heuristics, and applications of A*.Open →

What you need to know

Answer each one before you reveal it.

Take Algorithms further

The same content, four other ways.

Commonly confused

Pairs that lose marks when they are blurred together.

• Time complexity vs Space complexity

  Time complexity: how the running time of an algorithm grows as its input grows. Space complexity: how much additional memory an algorithm needs as its input grows.

• A static stack vs A dynamic stack

  A static stack: a structure of fixed size, decided when it is created and never changed. A dynamic stack: a structure that grows and shrinks as items are added and removed.

• A breadth-first traversal vs A depth-first traversal

  A breadth-first traversal: a traversal visiting every node at one distance before going any deeper. A depth-first traversal: a traversal following one path as far as it goes before backing up.

Questions from this topic

Each one with the model answer underneath.

1. 1

   What is an algorithm?

   Model answer

   A finite sequence of unambiguous steps that takes some input, carries out a defined process and produces an output, solving a problem or completing a task. It must be precise enough that it can be followed without judgement, and it must terminate rather than run forever.

2. 2

   A student says 'my program is my algorithm'. Why is that not quite right?

   Model answer

   An algorithm is the method itself, independent of any language. A program is one implementation of it. The same algorithm can be written in Python, in pseudocode, as a flowchart or in structured English, and it is still the same algorithm, so the method can be analysed and compared before a single line of code is written.

3. 3

   What are the first things you should establish when analysing a problem before designing an algorithm?

   Model answer

   What the inputs are and where they come from, what output is required and in what form, what processing turns one into the other, what data will be stored and in what structure, and what constraints apply such as how much data there will be, how fast it must run and how much memory is available.

4. 4

   Explain how decomposition helps in the design of an algorithm.

   Model answer

   Decomposition breaks a large problem into smaller sub-problems, each of which can be solved, tested and understood separately. It makes the design manageable, allows different sub-problems to be worked on independently or reused elsewhere, and means a fault can be located in one small part rather than across the whole solution.

5. 5

   What is a pre-condition, and why should an algorithm's design state it?

   Model answer

   A pre-condition is something that must be true before the algorithm is run for it to work correctly, for example that the list is already sorted or that the input value is positive. Stating it makes clear whose responsibility the check is, and prevents the algorithm being used in a situation where it will silently give a wrong answer.

6. 6

   Give three ways an algorithm can be expressed at the design stage.

   Model answer

   Structured English, pseudocode, and a flowchart. All three express the same logic; the choice is about who has to read it. Pseudocode is close enough to code to translate directly, a flowchart makes the flow of control visible, and structured English is easiest for a non-programmer to check.

What is inside Levo

Six ways to work the same material.

Algorithms revision questions

What does Algorithms cover in OCR A-Level Computer Science?

17 subtopics: designing and analysing an algorithm, measuring efficiency and big o notation, comparing algorithms and choosing one for a task, stacks, queues, linked lists, trees and binary search trees, traversing a tree: depth-first and breadth-first, bubble sort, insertion sort, merge sort, quick sort, comparing the four sorting algorithms, linear search, binary search, dijkstra's shortest path algorithm and the a* algorithm. Each one has its own page with questions and model answers.

How is Algorithms organised?

By the OCR H446 specification, subtopic by subtopic, so it matches the order you are taught it in.