A-level Computer Science₇₅₁₇

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.

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.

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.

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

Time complexity is O( n ).

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

Time complexity is O(log n ).

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

Time complexity is O(log n ).

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

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

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.