Fundamentals of Algorithms

Who made a famous short path algorithm?

Dijkstra (Dike-Struh)

What does a shortest path algorithm do?

Finds the shortest path between two nodes in a weight graph.

What are 2 ways to traverse a graph?

• Breadth

• Depth

What is Breadth First search?

A node is checked entirely first before moving onto the next.

What is Depth First search?

An entire branch is explored before backtrackingD and truly checking each node.

What are the 3 ways to traverse a tree?

• Pre-Order

• In-Order

• Post-Order

What type of trees are each of the 3 tree traversals meant for?

• Pre-Order and Post-Order work with any tree.

• In-Order is mainly meant to be used on Binary trees.

Why do we use Reverse Polish Notation?

• Eliminates need for brackets.

• Great use in Stacks

What does the Dijkstra Algorithm do?

Finds the shortest path between two nodes in a graph.

What are 2 sorting algorithms?

• Bubble

• Merge

What are 2 Searching Algorithms?

• Linear

• Binary

On what list can a Linear search be used?

Linear search can be used on any unordered list.

On what list can a binary search be used?

Binary searches can only be used on ordered lists.

What are the 2 ways RPN can be visualised?

• Infix

• Postfix