Fundamentals of Algorithms

What Fundamentals of Algorithms covers

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.

The 6 subtopics

Each one has its own page.

• Graph traversalRecall 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.Open →
• Tree traversalRecall 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.Open →
• Reverse Polish notationRecall questions on converting between infix and postfix, evaluating a postfix expression with a stack, and why the notation needs no brackets.Open →
• Searching algorithmsRecall 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.Open →
• Sorting algorithmsRecall 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.Open →
• Optimisation algorithmsRecall questions on what Dijkstra's algorithm computes, what is recorded for each vertex, why weights must be non-negative, and recovering the path itself.Open →

What you need to know

Answer each one before you reveal it.

Take Fundamentals of Algorithms further

The same content, four other ways.

Commonly confused

Pairs that lose marks when they are blurred together.

• Breadth-first search vs Depth-first search

  Breadth-first search: a traversal using a queue to visit nearby vertices first. Depth-first search: a traversal using a stack or recursion to follow one route deeply.

• Linear search vs Binary search

  Linear search: a sequential inspection that works on unordered data. Binary search: a halving search that requires ordered data.

• Bubble sort vs Merge sort

  Bubble sort: an adjacent-swap method making repeated passes. Merge sort: a divide-and-conquer method combining ordered sublists.

Questions from this topic

Each one with the model answer underneath.

1. 1

   What does it mean to traverse a graph?

   Model answer

   To visit every vertex of the graph exactly once, following the edges, in a systematic order defined by the traversal algorithm. Because a graph may contain cycles, the traversal must record which vertices have already been visited so that it does not go round for ever.

2. 2

   Describe how a breadth-first search works.

   Model answer

   Start at a chosen vertex, mark it as visited and add it to a queue. Then repeatedly take the vertex at the front of the queue, examine each of its neighbours in turn, and for every neighbour not already visited mark it as visited and add it to the rear of the queue. Continue until the queue is empty. The effect is to visit all the vertices one edge from the start, then all those two edges away, and so on outwards in layers.

3. 3

   Describe how a depth-first search works.

   Model answer

   Start at a chosen vertex, mark it as visited and push it onto a stack. Then repeatedly look at the vertex on top of the stack: if it has an unvisited neighbour, mark that neighbour as visited and push it on top; if it has none, pop it and backtrack to the vertex beneath. Continue until the stack is empty. The effect is to follow one path as far as it will go before backtracking to try alternatives. It can equivalently be written recursively, with the call stack doing the same job.

4. 4

   Which data structure does each of breadth-first and depth-first search use, and why?

   Model answer

   Breadth-first search uses a queue. Because a queue is first in, first out, vertices are dealt with in the order they were discovered, so nearer vertices are always explored before further ones. Depth-first search uses a stack. Because a stack is last in, first out, the most recently discovered vertex is explored next, which drives the search deeper along one path and provides the backtracking when a dead end is reached.

5. 5

   A graph has vertices A, B, C, D, E, F and undirected edges A-B, A-C, B-D, C-E, D-F and E-F. Give the breadth-first traversal from A, taking neighbours in alphabetical order.

   Model answer

   A, B, C, D, E, F. A is visited and queued. Taking A, its neighbours B and C are visited and queued. Taking B, its unvisited neighbour D is visited and queued. Taking C, its unvisited neighbour E is visited and queued. Taking D, its unvisited neighbour F is visited and queued. Taking E, its neighbours C and F are already visited. Taking F, both its neighbours are visited, and the queue is empty.

6. 6

   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.

   Model 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.

What is inside Levo

Six ways to work the same material.

Fundamentals of Algorithms revision questions

What does Fundamentals of Algorithms cover in AQA A-Level Computer Science?

6 subtopics: graph traversal, tree traversal, reverse polish notation, searching algorithms, sorting algorithms and optimisation algorithms. Each one has its own page with questions and model answers.

How is Fundamentals of Algorithms organised?

By the AQA 7517 specification, subtopic by subtopic, so it matches the order you are taught it in.