Algorithm Study Guide

Front

What are the two main graph traversal algorithms?

Back

Breadth-First Search (BFS) and Depth-First Search (DFS).

Front

What data structure does BFS use?

Back

A queue (FIFO - First-In, First-Out).

Front

What data structure does DFS use?

Back

A stack (LIFO - Last-In, First-Out).

Front

What is the key difference between BFS and DFS?

Back

BFS explores all neighbours at the present depth before moving to the next level, while DFS explores as far as possible along each branch before backtracking.

Front

What are the three types of tree traversal algorithms?

Back

Pre-order, in-order, and post-order traversal.

Front

What is the order of nodes in pre-order traversal?

Back

Node, Left, Right.

Front

What is the order of nodes in in-order traversal?

Back

Left, Node, Right.

Front

What is the order of nodes in post-order traversal?

Back

Left, Right, Node.

Front

What is Reverse Polish Notation (RPN)?

Back

A notation where the operator follows the operands (e.g., AB+).

Front

How is RPN evaluated?

Back

Using a stack: push operands onto the stack, pop the last two operands when encountering an operator, perform the calculation, and push the result back onto the stack.