4.3 Fundamentals of algorithms

4.3.1 Graph-traversal

4.3.1.1 Simple graph-traversal algorithms

Content

Additional information

Be able to trace breadth-first and depth-first search algorithms and describe typical applications of both.

Breadth-first: shortest path for an unweighted graph.

Depth-first: Navigating a maze.

4.3.2 Tree-traversal

4.3.2.1 Simple tree-traversal algorithms

Content

Additional information

Be able to trace the tree-traversal algorithms:

  • pre-order
  • post-order
  • in-order.
 

Be able to describe uses of tree-traversal algorithms.

Pre-Order: copying a tree.

In-Order: binary search tree, outputting the contents of a binary search tree in ascending order.

Post-Order: Infix to RPN (Reverse Polish Notation) conversions, producing a postfix expression from an expression tree, emptying a tree.

4.3.3 Reverse Polish

4.3.3.1 Reverse Polish – infix transformations

Content

Additional information

Be able to convert simple expressions in infix form to Reverse Polish notation (RPN) form and vice versa. Be aware of why and where it is used.

Eliminates need for brackets in sub-expressions.

Expressions in a form suitable for evaluation using a stack.

Used in interpreters based on a stack for example Postscript and bytecode.

4.3.4 Searching algorithms

Content

Additional information

Know and be able to trace and analyse the complexity of the linear search algorithm.

Time complexity is O(n).

Content

Additional information

Know and be able to trace and analyse the time complexity of the binary search algorithm.

Time complexity is O(log n).

Content

Additional information

Be able to trace and analyse the time complexity of the binary tree search algorithm.

Time complexity is O(log n).

4.3.5 Sorting algorithms

4.3.5.1 Bubble sort

Content

Additional information

Know and be able to trace and analyse the time complexity of the bubble sort algorithm.

This is included as an example of a particularly inefficient sorting algorithm, time-wise. Time complexity is O(n2).

4.3.5.2 Merge sort

Content

Additional information

Be able to trace and analyse the time complexity of the merge sort algorithm.

The 'merge' sort is an example of 'Divide and Conquer' approach to problem solving. Time complexity is O(nlog n).

4.3.6 Optimisation algorithms

4.3.6.1 Dijkstra’s shortest path algorithm

Content

Additional information

Understand and be able to trace Dijkstra’s shortest path algorithm.

Be aware of applications of shortest path algorithm.

Students will not be expected to recall the steps in Dijkstra's shortest path algorithm.