4.3 Algorithms

Question 1

Name an application of breadth-first search

Answer 1

Finding the shortest path for an unweighted graph

Question 2

Name an application of depth-first search

Answer 2

Navigating a maze

Question 3

2 differences between depth-first traversal and breadth-first traversal

Answer 3

DF: Chooses to explore the most recent node to be discovered
BF: Chooses to explore the least recent node to be discovered

DF: Implemented using a stack (when implemented iteratively)
BF: Implemented using a queue (when implemented iteratively)

Question 4

Depth-first traversal algorithm (beyond spec)

Answer 4

Each node has a binary flag discovered which is updated whenever we pop a node off the stack and consider its neighbours

1. Add the start node to the stack and mark it as discovered
2. If the stack is empty, we’re done. Otherwise, pop the top node and visit it
3. Push each of the current node’s undiscovered neighbours to the stack, and mark them as discovered
4. Go back to step 2

Question 5

Breadth-first traversal algorithm (beyond spec)

Answer 5

Each node has a binary flag discovered which is updated whenever we dequeue an item and consider its neighbours

1. Add the start node to the queue and mark it as discovered
2. If the queue is empty, we’re done. Otherwise, dequeue the front node and visit it
3. Enqueue each of the current node’s undiscovered neighbours to the queue, and mark them as discovered
4. Go back to step 2

Question 6

What is tree traversal?

Answer 6

Visiting the nodes of a tree in a specific order

Question 7

Use of pre-order traversal

Answer 7

Copying a tree

Question 8

2 uses of in-order traversal

Answer 8

• Outputting the contents of a binary search tree in ascending order
• Producing infix expression from an expression tree

Question 9

2 uses of post-order traversal

Answer 9

• Infix to RPN conversions
• Producing a postfix (RPN) expression from an expression tree

Question 10

Pre-order traversal operation

Answer 10

1. Visit the node
2. Traverse the left hand sub tree
3. Traverse the right hand sub tree

Question 11

In-order traversal operation

Answer 11

1. Traverse the left hand sub tree
2. Visit the node
3. Traverse the right hand sub tree

Question 12

Post-order traversal operation

Answer 12

1. Traverse the left hand sub tree
2. Traverse the right hand sub tree
3. Visit the node

Question 13

3 advantages of RPN

Answer 13

• Eliminates need for brackets in sub-expressions
• There is no need for precedence of operators
• The expressions are in a from suitable for evaluation using a stack, as the expression can be evaluated from left to right

Question 14

Steps for converting postfix to infix (2*)

Answer 14

• Convert “num num op” triplets one at a time, adding brackets each time
• Remove any unnecessary brackets

Question 15

Steps for converting infix to postfix (3•)

Answer 15

• Add brackets around every operation
• Draw arrow from operator to end of its bracket
• Write expression, keeping numbers in the same order

Question 16

Steps for linear search on a list

Answer 16

1. Start at beginning of list
2. Compare each item to one you want until
   
   • you find it or
   • you reach the end of the list

(use an indefinite while loop!)

Question 17

Steps for binary search on a value X (in English)

Answer 17

1. Look at item in centre of sorted list (or array) (sort first if needed)
2. If it isn’t X…
   2.1. If it is larger than X, you can ignore all of the items above
   2.2. If it is smaller than X, you can ignore all of the items below
3. Check middle of halved list and repeat, until you find X or the sublist cannot be halved any more.

Question 18

What is the while condition when coding binary search?

Answer 18

lower<= upper && !found

Question 19

What does it mean if you reach a leaf node before you find X in a binary tree search?

Answer 19

X is not in the tree

Question 20

Why is space complexity important to consider when analysing binary tree search?

Answer 20

Because the algorithm is recursive, it places a demand on the call stack

Question 21

Bubble sort (ascending order) pseudocode on array A

Answer 21

N ← length(A)
swapped ← True
while swapped and N > 1:
__swapped ← False
__for position = 0, 1, ... , N-2:
____if A[position] > A[position+1]:
______swap( A[position] , A[position+1])
______swapped ← True
__N ← N-1

Question 22

Merge sort complexity

Answer 22

O(n log n)

Question 23

What is an algorithm?

Answer 23

A sequence of unambiguous steps that can be followed to complete a task and that always terminates

Question 24

2 reasons why smaller time complexity is better

Answer 24

• A quicker program could solve more of the same problem or run more programs in the same time period
• Computers consume electricity to run…

Question 25

2 reasons why is smaller space complexity better

Answer 25

- A program that uses less memory could run off cheaper hardware (as less RAM is needed) - Or a greater number of different algorithms can run on the same hardware simultaneously

Question 26

What is the purpose of Dijkstras algorithm? Can the graph be directed/weighted?

Answer 26

- Calculates the shortest path between a node and all other nodes in a graph - Graph may be directed or undirected - Graph must be weighted

Question 27

What approach does merge sort take to sort a list?

Answer 27

Divide and conquer

Question 28

What is bubble sort's time complexity? Why?

Answer 28

O(n^2). Since it involves a for loop within a for loop. You need to do n passes of the list/array, and each pass involves swapping all the way down the list.