Set 9

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

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

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

Steps for linear search on a list

Answer 13

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 14

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

Answer 14

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 15

What is the while condition when coding binary search?

Answer 15

lower<= upper && !found

Question 16

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

Answer 16

X is not in the tree

Question 17

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

Answer 17

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

Question 18

Merge sort complexity

Answer 18

O(n log n)

Question 19

2 reasons why smaller time complexity is better

Answer 19

• 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 20

2 reasons why is smaller space complexity better

Answer 20

• 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 21

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

Answer 21

• 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 22

What approach does merge sort take to sort a list?

Answer 22

Divide and conquer

Question 23

What is bubble sort’s time complexity? Why?

Answer 23

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.

Question 24

Hierarchy of complexities (polynomial, logarithmic, constant, exponential, linear)

Answer 24

constant < logarithmic < linear < polynomial < exponential