3 Fundementals of algorithms

Depth vs Breadth first traversal: Data types

D : Stack

B : Queue

Depth vs Breadth first traversal: Implementation

D : Usually recursive (or iterative with explicit stack)

B : Usually iterative (with a while loop)

Depth vs Breadth first traversal: Use case

D : Navigating a maze

B : Shortest path on an unweighted graph

Depth vs Breadth first traversal: Required graph state

Connected for both (no orphans)

What is a tree-traversal?

It is a form of depth-first traversal that must start at the root.

Three properties for a graph to be a tree?

It must:

• contain no cycles

• be connected

• be undirected.

What defines a "Rooted Tree" and a "Binary Tree"?

• Rooted Tree: A tree where one vertex is designated as the root, creating parent-child relationships.

• Binary Tree: A rooted tree where each node has at most two children.

What is the primary use of a PRE-ORDER tree traversal?

Copying a tree.

What is the primary use of an IN-ORDER tree traversal?

Outputting the contents of a binary search tree in ascending (alphabetical/numerical) order.

Which tree-traversal method is ONLY well-defined for binary trees?

In-order traversal

State three uses of a POST-ORDER tree traversal.

1. Infix to RPN (Reverse Polish Notation) conversions;

2. Producing a postfix expression from an expression tree;

3. Emptying a tree.

What is an expression tree?

A tree where the internal parent nodes contain an opcode (operator) and the leaf/child nodes contain an operand.

How is a single stack used to evaluate a RPN expression? (4)

(Starting at LHS of expression) push operands on to stack

Each time operator reached pop top two values off stack

Push result (of applying operator) to stack

When end of expression is reached the top item of the stack is the result

What are the main advantages of using Reverse Polish Notation?

• Eliminates the need for brackets in sub-expressions.

• Simpler for a computer to evaluate.

Where is Reverse Polish Notation typically used in computer systems?

In interpreters based on a stack (e.g., Postscript and bytecode).

What is the time complexity of the Linear Search algorithm?

O(n)

Explain why Linear Search has a time complexity of O(n).

Each item in the
list is compared sequentially to the target. In the worst case, the loop repeats
n times to check every single item.

What is the strict prerequisite condition for performing a Binary Search?

The list must be ordered (sorted).

What is the time complexity of the Binary Search algorithm?

O(log n)

Explain why Binary Search has a time complexity of O(log n).

Every
comparison halves the size of the search space remaining to look at, which
mathematically represents a logarithmic reduction.

What is the time complexity of a Binary Tree Search algorithm?

O(log n)

Explain why a Binary Tree Search has a time complexity of O(log n).

Assuming
the binary search tree is balanced, choosing to branch left or right at each
node eliminates half of the remaining subtree at each step.

What is the time complexity of the Bubble Sort algorithm?

O(n²)

Explain why Bubble Sort has a time complexity of O(n²).

There are n items.
In the worst case, it requires n passes through the list, and each pass makes up
to n comparisons (n × n = n²).

How can the bubble sort be optimised? (2)

• Add an early exit flag: Use a boolean flag to track whether any swaps occurred during a pass, and terminate the outer loop early if no swaps were made.

• Reduce the inner loop range: Decrease the inner loop’s upper limit by 1 after each pass to avoid re-checking elements that are already sorted.

What is the time complexity of the Merge Sort algorithm?

O(n log n)

Explain why Merge Sort has a time complexity of O(n log n).

Halving the list
repeatedly takes log₂ n divisions (levels). Merging the sublists back together
requires examining all n items at each level (n × log n).

What is the primary purpose of Dijkstra's algorithm?

To find the shortest
path between two nodes in a weighted graph.

What data structure is typically used to implement Dijkstra's algorithm
efficiently?

Priority Queue.

To what types of graphs can Dijkstra's algorithm be applied in terms of direction and edge weight?

Direction: Can be used with both directed and undirected graphs.

Weight: Can only be used with weighted graphs.

State two typical real-world applications of Dijkstra's algorithm.

1. Satellite navigation systems (displaying the shortest/fastest route).

2. Network routers (finding the shortest path when routing packets).

When setting up a table to trace Dijkstra's algorithm, what initial tentative distances are assigned to the start node and all other nodes?

The start node is assigned a tentative distance of 0, and all other unvisited nodes are assigned infinity (∞).

When tracing Dijkstra's algorithm, under what condition is an unvisited
neighbour's tentative distance updated?

If the calculated distance to the
neighbour via the current node is less than its currently recorded tentative
distance.