Fundamentals of Algorithms

Question 1

What is an algorithm?

Answer 1

A set of instructions that completes a task in a finite time and always terminates

Question 2

What is Graph Traversal?

Answer 2

Visiting each vertex in a graph

Question 3

Two types of Graph Traversal?

Answer 3

Depth first search and breadth first search

Question 4

Which traversal is best for navigating a maze?

Answer 4

Depth-first search

Question 5

What is Breadth-first traversal useful for?

Answer 5

Shortest path on an unweighted graph

Question 6

What abstract data type is used for breadth-first traversal?

Answer 6

Queue

Question 7

What abstract data type is used in depth-first traversal

Answer 7

Stack

Question 8

What types of graphs can be traversed?

Answer 8

Connected graphs

Question 9

Can a tree undergo depth-first traversal?

Answer 9

Yes, but you might want to use tree-traversal instead

Question 10

Can a graph traversal start from any node?

Answer 10

Yeah

Question 11

What is tree-traversal?

Answer 11

Visiting/outputting each node in a tree; it’s an algorithm

Question 12

Three types of tree-traversal

Answer 12

Preorder, inorder and postorder

Question 13

Name a use of post-order traversal

Answer 13

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

Question 14

TRICK: Where does the dot go for you to trace the tree for post-order traversal?

Answer 14

To the right

Question 15

TRICK: Where does the dot go for you to trace the tree for in-order traversal?

Answer 15

Below

Question 16

TRICK: Where does the dot go for you to trace the tree for pre-order traversal?

Answer 16

To the left

Question 17

Traversal used for copying a tree?

Answer 17

Pre-order traversal

Question 18

Name a use of inorder traversal

Answer 18

Output the contents of a binary search tree in ascending order

Question 19

Can inorder traversal be performed on any tree?

Answer 19

NO! Only binary trees

Question 20

Can preorder traversal be performed on any tree?

Answer 20

YES!

Question 21

Can postorder traversal be performed on any tree?

Answer 21

YES!

Question 22

Where does tree traversal start?

Answer 22

At the root

Question 23

How do traversals work their way through the tree?

Answer 23

Anti-clockwise

Question 24

What is true about RPN?
A. Uses queue
B. Eliminates needs for brackets
C. Based on graph

Answer 24

B

Question 25

Convert infix expression to RPN:
14 + 6

Answer 25

14 6 +

Question 26

Convert infix expression to RPN
(12 - 4) x (3 + 5)

Answer 26

12 4 - 3 5 + x

Question 27

Convert the following RPN to infix
13 6 + 4 -

Answer 27

(13 + 6) - 4

Question 28

Convert the following infix expression to RPN
3(4 - 2) + 9

Answer 28

4 2 - 3 x 9 +

Question 29

Convert the RPN
4 6 7 + - to Infix

Answer 29

4 - (6 + 7)

Question 30

Which of the following is not an example where reverse Polish is used?
A. PreScript
B. Bytecode
C. PostScript

Answer 30

A

Question 31

What is the result of this reverse Polish expression?
4 6 8 - -

Answer 31

6

Question 32

What is the purpose of an optimisation algorithm?

Answer 32

To find the best possible solution to the problem posed

Question 33

Purpose of Dijkstra’s algorithm?

Answer 33

Find the shortest path between two nodes in a network

Question 34

Where is Dijkstra’s algorithm used?

Answer 34

Satellite navigation and packet routing

Question 35

Which is the most time efficient: bubble sort or merge?

Answer 35

Merge sort

Question 36

Which sorting algorithm is an example of a “divide and conquer” algorithm?

Answer 36

Merge sort

Question 37

Time complexity of a bubble sort algorithm?

Answer 37

O(n^2)

Question 38

Time complexity of the merge sort algorithm?

Answer 38

O(nlogn)