Algorithms

Question 1

Breadth-First Traversal

Answer 1

Graph traversal algorithm that uses a queue to store visited nodes.

Starts at the first node then visits all its neighbours, then visits their neighbours until all the nodes have been visited

A vertex is added to the queue when visited and removed when the algorithm moves on to its neighbours

Used to find the shortest path for an unweighted graph

Question 2

Depth-First Traversal

Answer 2

Graph traversal algorithm that uses a stack to store visited nodes

Starts at the first node, then follows an edge until a dead end is reached, then backtracks up to a vertex and reapplies the algorithm until all nodes are visited

Used in pathfinding algorithms, eg through a maze

Question 3

Depth-First Traversal Types

Answer 3

Pre-order = Visiting the root node, then the left subtree, then the right subtree
- Used to copy a tree
- Output is before recursive calls

In-order = Left subtree, then the root node, then the right subtree
- Output a binary search trees contents
- Output is in between recursive calls

Post-order = Left subtree, then the right subtree, then the root node
- Convert infix expression to postfix notation
- Output is after recursive calls

Question 4

Linear Search - O(n)

Answer 4

Search algorithm that starts at the beginning of the data structure and compares each data item one by one until the item is found or until the algorithm reaches the end of the data structure

Time complexity = O(n)

Question 5

Binary Search -
O(log2 n)

Answer 5

Search algorithm that repeatedly divides the search area (the data structure) into 2 until the data item is found

CAN ONLY BE DONE ON SORTED DATA

2 pointers are used to indicate the upper and lower bounds of the search area

The key of the required record is compared to the key of the record in the middle of the search area - if the needed key is larger than the middle key, the top half of the search area is checked (Bottom = Mid + 1)
If the needed key is smaller than the middle key, the bottom half is searched (Top = Mid - 1)

Time complexity = O(log2 n)

Question 6

Binary Sort - O(n^2)

Answer 6

Algorithm that compares neighbouring elements to each other, starting from the start of the list

If the elements are in the wrong order they are swapped around.

The next 2 elements are compared until the end of the list is reached - the process is then repeated at the start of the list until the list is sorted

Time complexity = O(n^2)

Question 7

Merge Sort - O(n log n)

Answer 7

Algorithm that uses a divide and conquer approach to sorting a list.

It divides the unsorted lists into halves and keeps going until each sublist contains 1 element, then the algorithm merges each sublist to produce new sorted sublists until only one list is left - the sorted list

Time complexity = O(n log n)

Question 8

Binary Tree Searching

Answer 8

Starting from the root node, the required item is compared to the node

• If they are equal the item has been found
• If the required item is less than the node, the search moves to the left sub-tree
• If the required item is greater than the node, the search moves to the right sub-tree

The search continues until the item is found or until a terminator is reached - the item doesnt exist in the tree

Question 9

Dijkstra’s Algorithm

Answer 9

An algorithm designed to find the shortest path between a start node and every other node in a WEIGHTED graph

Used in route planning and network optimisation

Question 10

Reverse Polish Notation

Answer 10

Expression notation where the operator is placed after the operands it acts on
eg. 3+4 in RPN is 3 4 +
Infix = operator is in between the operands

Benefits include:
- Unambiguous and simpler for a machine to evaluate
- Not limited to a certain number of operations