Topic 3

What is an algorithm?

A set of instructions which completes a task in a finite time and always terminates.

What is Graph Traversal?

The process of visiting each vertex in a graph

Name the two types of graph traversal.

Depth-first search and breadth-first search.

Which traversal is best for navigating a maze?

Depth-first search

What is Breadth-first traversal useful for?

Shortest path on an unweighted graph

What abstract data type is used for a breadth-first traversal?

Queue

What abstract data type is used in a depth-first traversal?

Stack

What type of graphs can be traversed?

Connected graphs

Can a tree undergo depth-first traversal?

Yes, although it might be more appropriate to use a tree-traversal

Can a graph traversal start from any node?

Yes.

In what order would these nodes be discovered in a breadth-first search, starting from node A (edges: A-B, A-C, B-D, B-E)?

A B C D E

In what order would these nodes be discovered in a depth-first search, starting from node A (edges: A-B, A-C, B-D, B-E)?

A B D E C

What is tree-traversal?

The process of visiting/updating/outputting each node in a tree; it is an algorithm

What is an algorithm?

A set of instructions which completes a task in a finite time and always terminates.

Name the three types of tree-traversal.

Preorder, inorder and postorder.

Name a use of postorder traversal.

Emptying a tree; infix to RPN conversions; producing a postfix expression from an expression tree

Which traversal would be used for copying a tree?

Preorder traversal

Name a use of inorder traversal.

Outputting the contents of a binary search tree in ascending order

Can inorder traversal be performed on any tree?

No, only binary trees (including binary search trees)

Can preorder traversal be performed on any tree?

Yes

Can postorder traversal be performed on any tree?

Yes

Where does tree traversal start?

At the root

How do traversals work their way around the tree?

Anticlockwise

What is the output when an inorder traversal is performed on this tree

Lily, Enid, Susan, Beth, Imogen, Amy, Niamh

What is the output when a postorder traversal is performed on this tree

Lily, Susan, Enid, Imogen, Niamh, Amy, Beth

What is the output when a preorder traversal is performed on this tree

Beth, Enid, Lily, Susan, Amy, Imogen, Niamh

Which of the following is true of reverse Polish notation? (A: uses a queue, B: eliminates the need for brackets, C: based on graphs)

It eliminates the need for brackets

Convert the following infix expression to reverse Polish 14 + 6

14 6 +

Convert the following infix expression to reverse Polish (12 - 4) × (3 + 5)

12 4 - 3 5 + ×

Convert the following reverse Polish expression to infix 13 6 + 4 -

(13 + 6) - 4

Convert the following infix expression to reverse Polish 3(4 - 2) + 9

4 2 - 3 × 9 +

Convert the following reverse Polish expression to infix 4 6 7 + -

4 - (6 + 7)

Which of the following is not an example of where reverse Polish is used? (A: PreScript, B: Bytecode, C: PostScript)

PreScript

What is the result of this reverse Polish expression? 2 8 × 2 4 - ×

-32

What is the result of this reverse Polish expression? 4 6 8 - -

6

What is a searching algorithm used for?

A searching algorithm is used to find a specified data item within a set of data

Time complexity of linear search

O(N)

What must be true about a set of data if it is to be searched using the binary search algorithm?

The set of data must be sorted

Which is most efficient, binary search or linear search?

Binary search

Time complexity of binary search

O(LogN)

Calculation used to find the midpoint of a set of data

Add the first and last positions of the data, and divide by two

Time complexity of binary tree search

O(LogN)

What is a binary tree?

A rooted, ordered tree in which each node has no more than 2 children

Which sorting algorithm is most time efficient: bubble sort or merge sort?

Merge sort

Which sorting algorithm is an example of a "divide and conquer" algorithm?

Merge sort

What is the time complexity of the bubble sort algorithm?

O(n2)

What is the time complexity of the merge sort algorithm?

O(nlogn)

Sort this array into ascending order using the bubble sort algorithm: 4 3 5 7 6

4 3 5 7 6 -> 3 4 5 7 6 -> 3 4 5 7 6 -> 3 4 5 6 7

Sort this array into ascending order using the merge sort algorithm: Tom Sue Jack Bill Ada

Ada Bill Jack Sue Tom

What is the purpose of an optimisation algorithm?

To find the best possible solution to the problem posed

What is the purpose of Dijkstra's algorithm?

To find the shortest path between two nodes in a network

Which of the following is not an example of where Dijkstra's algorithm is used? (A: Satellite navigation, B: Binary tree search, C: Packet routing)

Binary tree search

Which table shows Dijkstra's algorithm carried out on this graph

C