Fundamentals of Algorithms | AQA A-Level Computer Science (7517)

Fundamentals of Algorithms

82 questions
6 subtopics
Paper 1: the on-screen exam
Paper 1

Graph and tree traversal, Reverse Polish notation, searching, sorting and Dijkstra's shortest path algorithm, each with the time complexity it is judged by.

Examined on Paper 1.

Sample questions from Fundamentals of Algorithms

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

Graph traversal

Using the same graph — vertices A to F with edges A-B, A-C, B-D, C-E, D-F and E-F — give the depth-first traversal from A, taking neighbours in alphabetical order.

Show the answer
A, B, D, F, E, C. From A the first unvisited neighbour is B, from B it is D, from D it is F, from F the unvisited neighbour is E, and from E it is C. C has no unvisited neighbours, so the search backtracks all the way, popping E, F, D, B and A in turn, and finishes.
Graph traversal

Give the typical application of breadth-first search.

Show the answer
Finding the shortest path in an unweighted graph. Because breadth-first search explores outwards in layers, the first time it reaches a vertex it has done so using the fewest possible edges, so the path it found is the shortest one.
Tree traversal

Describe the post-order traversal algorithm.

Show the answer
Starting at the root: apply the procedure recursively to the left subtree, then apply it recursively to the right subtree, and only then output the value at the current node. If a subtree is empty, nothing is done for it and the algorithm returns.
Tree traversal

For the same tree — root A, children B and C; B has children D and E; C has right child F — give the post-order traversal.

Show the answer
D, E, B, F, C, A. The left subtree rooted at B gives D, E, B; the right subtree rooted at C gives F, C; and the root A is output last.
Reverse Polish notation

Convert (3 + 4) * 5 to Reverse Polish notation.

Show the answer
3 4 + 5 *. The bracketed subexpression 3 + 4 becomes 3 4 +, and that result is then multiplied by 5, so the operands 3 4 + and 5 are followed by the operator *.
Reverse Polish notation

Convert 7 2 3 * - from Reverse Polish notation to infix form and evaluate it.

Show the answer
Working left to right, 2 3 * means 2 * 3, and then 7 followed by that result and the operator - means 7 - (2 * 3). The infix form is 7 - 2 * 3, which evaluates to 7 - 6 = 1.
Searching algorithms

What is the time complexity of linear search, and what does it mean?

Show the answer
O(n). In the worst case, when the item is the last in the list or is not present at all, every one of the n items must be examined, so the time taken grows in direct proportion to the number of items. Doubling the length of the list doubles the expected time.
Searching algorithms

Trace a binary tree search for 6 in a tree with root 8, left child 3 and right child 10, where 3 has children 1 and 6 and 10 has a right child 14.

Show the answer
Start at the root, 8. 6 is less than 8, so follow the left branch to 3. 6 is greater than 3, so follow the right branch to 6. 6 equals 6, so the value is found. The search took three comparisons.

The 6 subtopics

One subtopic is one session. Work down the list.

Subtopic	What it covers	Questions
Graph traversal	Recall questions on breadth-first and depth-first search, the queue and stack each depends on, why visited vertices are recorded, and tracing both on a small graph.	12
Tree traversal	Recall questions on pre-order, in-order and post-order traversal, what each is used for, and producing all three orders for a given binary tree.	15
Reverse Polish notation	Recall questions on converting between infix and postfix, evaluating a postfix expression with a stack, and why the notation needs no brackets.	12
Searching algorithms	Recall questions on linear and binary search, their time complexities, the number of comparisons each makes, and tracing a search that succeeds and one that fails.	18
Sorting algorithms	Recall questions on bubble sort and merge sort, the effect of the swap flag, their time complexities, and how the running time grows as the list gets longer.	16
Optimisation algorithms	Recall questions on what Dijkstra's algorithm computes, what is recorded for each vertex, why weights must be non-negative, and recovering the path itself.	9

Fundamentals of Algorithms is 82 of the 1,516 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.