Fundamentals of Algorithms

What is a depth first traversal

Depth first traversal is a method for exploring tree or graph data structures where the algorithm starts at the root (or an arbitrary node) and explores as far as possible along each branch before backtracking.

How is a depth first traversal implemented

Using a stack

What is a breadth first traversal

Breadth first traversal is a method for exploring tree or graph data structures where the algorithm starts at the root (or an arbitrary node) and explores all of its neighbors before moving on to the next level of nodes.

How is a breadth-first traversal implemented

Using a queue

Pre-order traversal

Draw an outline around the tree structure. As you pass the left of a node, output the data in that node.

Where is a pre-order traversal used

generating prefix expressions used in functional programming languages.
Or copying a tree.

In-order traversal

Draw an outline around the tree structure. As you pass underneath a node output the data.

What is the use of an in-order traversal

outputting the contents of a binary search tree in ascending order .

Post-order traversal

Draw an outline around the tree structure. As you pass to the right of the node output the data in that node.

Use of a post-order traversal

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

How do you convert from infix to Reverse Polish (postfix) notation

Add brackets to establish operator precedence and then apply post-order traversal to record the expression.

Order of precedence (increasing order)

=
(
+-)
* /
^
~

How does a computer convert from infix to RPN

A process that involves the use of an expression tree to establish operator precedence, followed by a post-order traversal to generate the corresponding postfix notation.

How do you evaluate a RPN expression

You use a stack data structure to process the expression from left to right, pushing operands onto the stack and popping them for calculations whenever an operator is encountered.

Time complexity of a linear search

O(n)

Time complexity of a binary search

O(log n)

Time complexity of a bubble sort

O(n2)

Time complexity for a merge sort

O(n log n)

What is dijkstras shortest path algorithm

a graph algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph.

How does Dijkstra's shortest path algorithm work

It uses a priority queue to explore the graph by continually selecting the vertex with the smallest tentative distance.