Writing algorithms and code in the exam

Planning before writing, how code is marked, the standard algorithms to know by heart, and Dijkstra's algorithm driving the robot.

A15.5Exam preparationA level50 min

The questions that ask you to write an algorithm or a program carry the most marks on the programming papers, and they are the ones students most often leave half done. They are marked generously for partial solutions, if you know how the marks are given. This lesson is a method for writing code under exam conditions, and the standard algorithms you should be able to write from memory.

How code is marked

A code-writing mark scheme lists the features a correct answer contains, each worth a mark. For "write a function that returns the average of the readings above a threshold" (5 marks), a typical scheme is:

1. a function with the right parameters and a return;
2. a loop over every reading;
3. a correct comparison with the threshold;
4. a running total and a count of the readings that pass;
5. the average returned, with the case of no readings handled.

So an answer with a correct loop and comparison but a wrong average still earns 3 marks, and a blank earns nothing. Syntax errors that do not change the meaning usually cost nothing on paper; logic errors cost the mark for that feature. On screen (AQA paper 1) your code must actually run, and you paste in evidence of it working.

A method that works

1. Read the whole question twice. Underline the inputs, their types and ranges, what must be returned or output, and any restriction ("do not use a built-in sort").
2. Plan in comments or a few lines of pseudocode. Decide the data structures first: what is stored, and in what.
3. Write the skeleton: the subroutine header, the loop, the return. These are often marks on their own.
4. Fill in the body, one feature at a time, in the order the plan says.
5. Trace it with a small example, including an edge case: an empty list, one item, the target not present.
6. Tidy: meaningful names, consistent indentation, a comment where the reason is not obvious.

def average_above(readings, threshold):
    # plan: total and count only the readings above threshold; avoid dividing by zero
    total = 0
    count = 0
    for reading in readings:
        if reading > threshold:
            total += reading
            count += 1
    if count == 0:
        return 0
    return total / count

print(average_above([12, 40, 55, 8, 31], 30))   # (40 + 55 + 31) / 3
print(average_above([], 30))                    # the edge case

Run this in the simulator

Algorithms to know by heart

Some algorithms come up so often that you should be able to write them without thinking, in pseudocode and in your language, and state their complexity.

OCR also asks for A* search, which is Dijkstra's algorithm guided by a heuristic estimate of the distance still to go.

Dijkstra's algorithm, written to a plan

The delivery robot's corridors are a weighted graph (not to scale). The weight is the cost of the corridor: its length in cm, doubled on the carpet between A and B, where the robot is slow.

The plan:

set every distance to infinity, except the start, which is 0
while there are unvisited nodes
    current ← the unvisited node with the smallest distance
    mark current as visited
    if current is the goal then stop
    for each neighbour of current
        if distance[current] + weight < distance[neighbour] then
            distance[neighbour] ← distance[current] + weight
            previous[neighbour] ← current
rebuild the path by following previous back from the goal

The trace, from A to F:

Following previous back from F gives F, D, C, A, so the path is A, C, D, F with cost 100. The route through B looks shorter on the map, but the carpet makes it cost more.

Task: shortest route, then drive it

The robot stands at node A. coords gives each node's position as (x, y) in cm from A, where positive x is to the robot's right and positive y is straight ahead. graph is an adjacency list: graph[node] is a dictionary from each neighbour to the whole-number weight of the corridor.

1. Write dijkstra(graph, start, goal), which returns a tuple (path, cost): path is the list of node names from start to goal along the cheapest route, and cost is its total weight.
2. Call it for A to F and print path: <nodes>, with the nodes separated by single spaces, then cost: <cost>.
3. Drive the path, leg by leg. For each pair of consecutive nodes, work out dx and dy from coords. Move right dx cm if it is positive (left if negative), then forward dy cm if it is positive (backward if negative), at speed 50.
4. When the robot reaches the goal, turn the LED green.

Keep off the carpet between A and B.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

coords = {"A": (0, 0), "B": (0, 40), "C": (30, 0), "D": (30, 40), "E": (0, 70), "F": (30, 70)}
graph = {
    "A": {"B": 80, "C": 30},
    "B": {"A": 80, "D": 30, "E": 30},
    "C": {"A": 30, "D": 40},
    "D": {"B": 30, "C": 40, "F": 30},
    "E": {"B": 30, "F": 30},
    "F": {"D": 30, "E": 30},
}

def dijkstra(graph, start, goal):
    pass

Challenges

1. Change the carpet's weight to 40 and run it again. Which path does it choose, and is there a tie?
2. Write the mark scheme you would use for the dijkstra function if it were a 6-mark question.
3. Turn Dijkstra's algorithm into A* by adding the straight-line distance from each node to F as a heuristic. Does it visit fewer nodes?