4.3 Fundamentals of algorithms

Graph-traversal

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.

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.

Tree-traversal

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.

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.

Reverse Polish

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.

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.

Searching algorithms

Linear search

Content	Additional information
Know and be able to trace and analyse the complexity of the linear search algorithm.	Time complexity is O(n).

Binary search

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

Binary tree search

Content	Additional information
Be able to trace and analyse the time complexity of the binary tree search algorithm.	Time complexity is O(log n).

Sorting algorithms

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(n²).

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

Optimisation algorithms

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.

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.

Previous
4.2 Fundamentals of data structures

Next
4.4 Theory of computation