4.3 - Fundamentals of algorithms

Question 1

What are the applications of a breadth first search?

Answer 1

Finding the shortest path on an unweighted graph.

Question 2

What are the applications of a depth first search?

Answer 2

Navigating a maze.

Question 3

What is pre-order tree traversal used for?

Answer 3

Copying a tree.

Question 4

What is in-order tree traversal used for?

Answer 4

Navigating a binary search tree. Outputting the contents of a binary search tree in ascending order.

Question 5

What is post-order tree traversal used for?

Answer 5

Infix to RPN (Reverse Polish Notation) conversions, producing a postfix expression from an expression tree, emptying a tree.

Question 6

What are the benefits of reverse-polish?

Answer 6

Eliminates need for brackets in sub-expressions.

Question 7

What algorithm has a time complexity of O(log n)?

Answer 7

Binary tree/search.

Question 8

What algorithm has a time complexity of O(n^2)?

Answer 8

Bubble sort.

Question 9

What algorithm has a time complexity of O(nlog n)?

Answer 9

Merge sort.