Advanced algorithms (A Level) flashcards

Topic 11: Advanced algorithms

Breadth-first vs depth-first search

BFS visits vertices layer by layer outwards using a queue, and finds the fewest-edge path in an unweighted graph. DFS follows one branch as far as possible then backtracks, using a stack or recursion, e.g. to navigate a maze.

What does Dijkstra's algorithm find?

The shortest (lowest total weight) route from one vertex to all others in a weighted graph. At each step the unvisited vertex with the smallest total distance is picked and its distance becomes final.

Why is BFS not used for shortest routes in a weighted graph?

BFS counts edges and ignores weights, so a route with fewer edges can still cost more.

Give two applications of Dijkstra's algorithm

Satellite navigation and route planners, and routing data across networks (link-state protocols such as OSPF).

Pre-order, in-order and post-order traversal

Pre-order: node, left, right. In-order: left, node, right. Post-order: left, right, node.

What is each binary tree traversal used for?

Pre-order: copying a tree; prefix expressions. In-order: outputting a BST in ascending order. Post-order: postfix expressions; emptying a tree.

What is an expression tree?

A binary tree with operators at the internal nodes and operands at the leaves. Pre-order gives prefix notation and post-order gives postfix; neither needs brackets.

In code, how do the loop versions of BFS and DFS differ?

BFS removes from the front of the collection (a queue, e.g. popleft), while DFS removes from the end (a stack, e.g. pop).