A15.5 Writing algorithms and code in the exam worksheet

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

Questions 5 marks in all

[1 mark]Your code for a 5-mark question has a correct loop and comparison, but the final average is wrong. What is most likely?

AYou earn the marks for the features that are correct
BYou score 0 because it does not work
CYou lose a mark for every line
DOnly the return value is marked

[1 mark]What is the time complexity of merge sort?

AO(n log n)
BO(n²)
CO(log n)
DO(n)

[1 mark]Which algorithms require their input to meet a condition first?

Tick every answer that is true.

ABinary search: the list must be sorted
BDijkstra's algorithm: no negative edge weights
CLinear search: the list must be sorted
DBubble sort: the list must be sorted

[1 mark]This is the start of Dijkstra's algorithm on a small graph. What does it print?

graph = {"A": {"B": 4, "C": 1}, "B": {"D": 1}, "C": {"B": 2, "D": 6}, "D": {}}
dist = {n: float("inf") for n in graph}
dist["A"] = 0
unvisited = set(graph)
while unvisited:
    current = min(sorted(unvisited), key=lambda n: dist[n])
    unvisited.remove(current)
    for nb, w in graph[current].items():
        dist[nb] = min(dist[nb], dist[current] + w)
print(dist)

[1 mark]What does A* search add to Dijkstra's algorithm?

AA heuristic estimate of the distance still to go, to guide which node is visited next
BNegative edge weights
CA stack instead of a priority queue
DA limit of one path per node

The 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

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a15-5-writing-code-in-the-exam/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

Change the carpet's weight to 40 and run it again. Which path does it choose, and is there a tie?

Write the mark scheme you would use for the dijkstra function if it were a 6-mark question.

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?

What this lesson is about

Questions 5 marks in all

The task: shortest route, then drive it

Challenges