A-Level Computer Science: Insertion, Merge and Quick Sort, Dijkstra and A*

This material trains the standard algorithms of A level Computer Science that go beyond bubble sort and binary search: the three other sorts, and the two shortest-path algorithms. It is for Year 12 and Year 13 students who need to trace these algorithms by hand, state their complexity and choose between them.

The quiz has twelve questions. Six are about sorting. The student gives the state of a list after the third pass of an insertion sort and after the second round of a merge sort, and the result of one quick sort partition with the pivot rule stated in the question. The others ask which input gives quick sort its worst case, what merge sort costs in time and memory, which sort suits a list that is almost in order, and how many comparisons merging two sorted lists can take. Three questions use one weighted graph, given as a list of edges: the length of the shortest path from A to F, the order in which Dijkstra's algorithm makes nodes permanent, and why negative weights break the algorithm. The last two are about A*: which node on an open list is expanded next, given the cost so far and the heuristic for each, and what property the heuristic needs.

Every explanation traces the algorithm step by step. The graph questions show every distance update, including the direct-looking routes that turn out longer, and the A* question shows why the node with the lowest cost so far or the lowest estimate is not the right choice.

The flashcards cover the three sorts and their complexities, the quick sort worst case, merging, divide and conquer, stable sorting, how Dijkstra's algorithm updates distances and recovers the path, A* and its f = g + h rule, admissible heuristics and how A* compares with Dijkstra's algorithm.

The written work has eight longer tasks to answer on paper: every pass of an insertion sort, a full merge sort with the reason it is O(n log n), a complete quick sort with best and worst cases, a full run of Dijkstra's algorithm with the path recovered, A* compared with Dijkstra's algorithm, choosing a sort for three situations, insertion sort in pseudo-code, and divide and conquer in three algorithms. Each task has a model answer and the points a marker would look for.

There is also a short oral practice with an examiner, who gives every list and graph in full, states the exact convention for each trace and gives brief feedback at the end.

The content is based on the standard algorithms of the A level specifications, for example OCR H446 section 2.3.1 (insertion, merge and quick sort, Dijkstra's shortest path and A*) and AQA 7517 sections 4.3.5 and 4.3.6 (merge sort and Dijkstra's shortest path algorithm).

• Trace insertion sort, merge sort and quick sort pass by pass
• State and justify the best, average and worst-case complexity of each sort
• Choose a suitable sort for a given data set and memory limit
• Apply Dijkstra's algorithm to a weighted graph and recover the shortest path
• Explain why Dijkstra's algorithm needs non-negative weights
• Select the next node in A* using f = g + h and explain admissible heuristics

Practice material written by Zestly, based on the standard algorithms in the A level Computer Science specifications (for example OCR H446 section 2.3.1 and AQA 7517 sections 4.3.5 and 4.3.6).