Algorithms

Question 1

Graph Traversal

Answer 1

The process of visiting each vertex in a connected graph

Question 2

Depth First Search

Answer 2

• A branch is fully explored before backtracking
• Uses a stack
• Used for navigating a maze

Question 3

Breadth First Search

Answer 3

• A node is fully explored before venturing onto the next node
• Uses a queue
• Used for determining the shortest path on an unweighted graph

Question 4

Tree Traversal

Answer 4

• The process of visiting each node in a tree
• The algorithm must start at the root
• Works anticlockwise
• Uses Depth First Traversal

Question 5

Pre-Order Traversal

Answer 5

• Used for copying a tree
• Can be performed on any tree

Question 6

In-Order Traversal

Answer 6

Outputs the contents of a binary tree in ascending order

Question 7

Post-Order Traversal

Answer 7

• Can be performed on any tree
• Used to empty the tree
• Used for infix to RPN conversions

Question 8

Reverse Polish

Answer 8

A way of writing expressions with postfix notation

Question 9

Advantages of Reverse Polish

Answer 9

• It eliminates the needs for brackets, simplifying expressions
• Well suited for manipulation by a stack

Question 10

Searching Algorithm

Answer 10

Used to find a specified data item within a set of data

Question 11

Linear Search

Answer 11

• Can be conducted on any list
• Inspects every item one by one until the desired item is found
• Time complexity of O(N)

Question 12

Binary Search

Answer 12

• Only works on ordered lists
• Takes the midpoint of a list and determines if the target is higher or lower
• Time complexity of O(logN)

Question 13

Sorting Algorithms

Answer 13

Used to put elements in an array into a specific order

Question 14

Bubble Sort

Answer 14

• Swaps adjacent items in an array until the array is in order
• Has a time complexity of O(n^2)

Question 15

Merge Sort

Answer 15

• Divides an array into smaller arrays until each array contains just one element
• Arrays are then remerged into an ordered array
• Time complexity of O(nlogn)

Question 16

Optimisation Algorithms

Answer 16

Finds the best possible solution to the problem posed

Question 17

Dijkstra’s Algorithm

Answer 17

• Finds the shortest path from a starting node to every other node in a network
• Uses a priority queue rather than a standard queue

Question 18

Uses of Dijkstra’s Algorithm

Answer 18

• Satellite navigation systems
• Routers