Algorithms | OCR A-Level Computer Science (H446)

Algorithms

230 questions
17 subtopics
Component 02: Algorithms and programming
Component 02

Algorithms is examined on component 02 of OCR Computer Science, Algorithms and programming.

230 recall questions across 17 subtopics.

Sample questions from Algorithms

Answer each one closed book first, then open the answer.

Designing and analysing an algorithm

Explain how decomposition helps in the design of an algorithm.

Show the 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.
Comparing algorithms and choosing one for a task

Besides the number of operations, what else should you weigh when choosing an algorithm for a task?

Show the answer
How much memory it needs and how much is available, the size of the data set now and in the future, whether the data is already partly sorted, whether the data arrives all at once or item by item, whether equal items must keep their original order, and how complicated the algorithm is to implement correctly and maintain.
Queues

Describe the algorithm for removing an item from a queue.

Show the answer
Check whether the queue is empty; if it is, report the error and stop. Otherwise read the item at the position given by the front pointer, move the front pointer on by one, decrease the count of items held, and return the item read.
Trees and binary search trees

How do you find the smallest value in a binary search tree?

Show the answer
Start at the root and follow left children repeatedly until you reach a node with no left child. That node holds the smallest value, because every left move goes to smaller values and running out of left children means nothing smaller exists. Following right children instead finds the largest.
Bubble sort

What does an optimised bubble sort do on an already-sorted list of 100 items?

Show the answer
It makes one pass of 99 comparisons, performs no swaps, sees that the flag is still false and stops. That is 99 comparisons in total rather than the several thousand it would need on unsorted data, which is why the best case is linear.
Merge sort

Is merge sort stable, and why does that follow from the merge rule?

Show the answer
Yes. When the two front items being compared are equal, the merge takes the one from the left-hand list first. Since the left-hand list holds items that came earlier in the original data, equal items keep their original relative order.
Comparing the four sorting algorithms

Rank the four sorts for a list of a million random items and justify the ranking.

Show the answer
Quick sort first on speed, with merge sort close behind and preferable if the worst case must be excluded or stability is needed. Insertion sort and bubble sort are unusable: a million squared is of the order of a million million operations against roughly twenty million for the O(n log n) sorts.
Binary search

When is it not worth sorting the data first?

Show the answer
When the list will be searched only once or twice before it changes, and when the list is small enough that a linear pass is cheap anyway. If the data changes constantly, the sorted order has to be maintained on every insertion, and that continuing cost can outweigh the searching saved.

The 17 subtopics

One subtopic is one session. Work down the list.

Subtopic	What it covers	Questions
Designing and analysing an algorithm	Recall 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.	16
Measuring efficiency and Big O notation	Recall 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.	19
Comparing algorithms and choosing one for a task	Recall 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*.	12
Stacks	Recall 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.	12
Queues	Recall 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.	14
Linked lists	Recall 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.	12
Trees and binary search trees	Recall 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.	14
Traversing a tree: depth-first and breadth-first	Recall 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.	16
Bubble sort	Recall 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.	14
Insertion sort	Recall 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.	13
Merge sort	Recall 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.	14
Quick sort	Recall 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.	15
Comparing the four sorting algorithms	Recall 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.	8
Linear search	Recall 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.	10
Binary search	Recall 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.	14
Dijkstra's shortest path algorithm	Recall 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.	14
*The A algorithm**	Recall 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*.	13

Algorithms is 230 of the 1,549 questions in the guide.Get the guide, £9

How the guide is worked

Answering a question from memory stores it far better than reading the answer again. The guide runs that as a fixed procedure on one subtopic at a time, about twenty minutes a session.

Step 1 · Closed book
Cover the answers. Work through one subtopic and write down what you can. Leave blanks where you have nothing.
Step 2 · Open book
Go back to the top. Read each printed answer and write it out in full, including the ones you had right.
Step 3 · Closed book again
Same questions, same order, from memory. The gap between pass one and pass three is the session result.

Read the full method, the return schedule and the research behind it.