4.3 Algorithms

Question 1

Graph Traversal (definition)

Answer 1

visiting all the nodes on the graph

Question 2

Example of:
- Breadth First Search
- Depth First Search

Answer 2

• Breadth First: shortest path for an unweighted graph
• Depth First: navigating a maze

Question 3

Breadth First Search Process (5)

Answer 3

• enqueue root and add to visited list
• are there any nodes adjacent to the node at the front of the queue that haven’t been visited?
• • if so: enqueue node and add to visited list
• • if not: dequeue
• repeat process until queue is empty (all nodes have been visited)

Question 4

Depth First Search Process (5)

Answer 4

• push root node onto stack and add to visited list
• is there a node adjacent to the node at the top of the stack that has not been visited?
• • if so: push node onto stack and add to visited list
• • is not: pop off stack
• repeat process until stack is empty (all nodes have been visited)

Question 5

Pre Order: acronym, dot placement

Answer 5

• NLR (node, left , right)
• dot to the left

Question 6

In Order: acronym, dot placement

Answer 6

• LNR (left, node, right)
• dot underneath

Question 7

Post Order: acronym, dot placement

Answer 7

• LRN (left, right, node)
• dot to the right

Question 8

Examples Using Tree Traversal Algorithms

Answer 8

• Post Order: converts infix notation to RPN
• In Order: outputs contents of a binary search tree in ascending order

Question 9

Convert Infix to RPN: 3 + (4 * 2) - 1

Answer 9

3, 4, 2, *, +, 1, -

Question 10

Advantages of RPN over Infix Notation (2)

Answer 10

• simpler for a machine to evaluate
• RPN doesn’t require brackets, unlike infix notation

Question 11

Using a Stack to Evaluate RPN (5)

Answer 11

• if character in expression is a number: push value onto stack
• if character in expression is an operator:
• • pop last two values off the stack
• • apply the operator to the two values
• • push result onto stack
• repeat process until end of expression is reached
• pop top value off stack to give result

Question 12

Linear Search
- process (2)
- time complexity
- advantage

Answer 12

• iterates through each item in list and compares it to condition element
• only breaks if condition is met or program reaches end of the list
• time complexity: O(n)
• adv: data doesn’t need to be in order

Question 13

Binary Search
- process (1)
- time complexity
- disadvantage

Answer 13

• when searching, the index of the middle of the set is calculated by adding the leftmost and rightmost indexes and dividing by 2, discarding any remainder
• time complexity: O(log n)
• dis: data needs to be in order

Question 14

Binary Tree Search
- time complexity
- use
- advantage
- disadvantage

Answer 14

• time complexity: O(log n)
• rapid search of data
• adv: data does not need to be in order
• dis: it takes more memory to store the data (3 times the amount of data)

Question 15

Bubble Sort
- process (1)
- time complexity

Answer 15

• if swapped is still false at the end of a pass through the data then no swaps were made, which means the data is now in order and the sort can finish
• time complexity: O(n^2)

Question 16

Merge Sort
- process (2)
- time complexity

Answer 16

• follows a ‘divide and conquer’ approach
• uses a recursive technique
• average time complexity: O(n log n)

Question 17

Dijkstra’s Algorithm
- process (3)
- examples (2)

Answer 17

• finds the shortest path between a given node and all other nodes (graph must be weighted)
• stores nodes in a priority queue
• • rule: the node with smallest distance from start is dequeued
• e.g. use with GPS devices
• e.g. solving a Rubik’s cube