4.3 Fundamentals of Algorithms

Question 1

Graph traversals

Answer 1

Breadth-First Search – start at the root and scan every node connected, and then continue scanning from left to
right.

Depth-First Search – Start at the root, follow one branch as far as it will go, then backtrack.

Question 2

Tree traversals

Answer 2

• Pre-order Root <- ->
• Post-order <- -> Root
• In-order <- Root ->

Uses:
* Pre-Order: copying a tree.
* In-Order: binary search tree, outputting the contents of a binary search tree in ascending order. This is really
useful as the output is effectively been sorted, regardless of the order which the data was placed in to the
tree.
* Post-Order: Infix to RPN (Reverse Polish Notation) conversions, producing a postfix expression from an
expression tree, emptying a tree.

Question 3

What is reverse polish notation/postfix?

Answer 3

RPN is a mathematical notation that removes the use of parenthesis (brackets) in arithmetic expressions.

In other words, it means BIDMAS does not need to be used for any mathematical expression.

Question 4

Time complexities

Answer 4

Linear search - Time complexity is O(n).
Bubble Sort - Time complexity is O(n2).
Merge Sort - Time complexity is O(n log n).
Binary search - Time complexity is O(log n).

Question 5

Linear vs Binary search

Answer 5

Although linear and binary searching produces the same overall results, linear search is best used when the data is
not in order, or for smaller lists.
However, when the list is much longer and the data is in order, it is far more efficient to calculate the indexes
needed to perform a binary search.

Question 6

Bubble sort vs merge sort

Answer 6

The Bubble sort is a simple algorithm to understand, however it performs very poorly with a large list. A merge sort
is a very fast sort; however, it is more complicated to program.

Question 7

Dijkstra’s

Answer 7

Dijkstra’s algorithm works by working out the shortest path between a single source (a starting vertex) and every
other vertex. As the algorithm calculates all possible routes, it will also calculate the shortest route.

Applications of shortest path algorithms
* Satellite navigation systems and mapping
software.
* Telephone and computer network planning
* Network routing / packet switching
* Logistics and scheduling