3: Fundamentals of Algorithms Flashcards
Breadth-First Search Algorithm
Add start node to discovered list
Enqueue start node
While queue is not empty
Dequeue item to become current node
For each neighbour of current node
If neighbour is not in discovered list
Add neighbour to discovered list
Enqueue neighbour
Depth-First Search Algorithm
Add start node to discovered list
Push start node onto stack
While stack is not empty
Pop item from stack to become current node
For each neighbour of current node
If neighbour is not in discovered list
Add neighbour to discovered list
Push neighbour onto stack
Applications of Breadth-First Search Algorithm
Shortest path for an unweighted graph
Applications of Depth-First Search Algorithm
Navigating a maze
Uses of Pre-Order Tree Traversal
Copying a tree
Uses of In-Order Tree Traversal (2)
- Binary search tree
- Outputting contents of a binary search tree in ascending order
Uses of Post-Order Tree Traversal (3)
- Infix to RPN conversions
- Producing a postfix expression from an expression tree
- Emptying a tree
Infix Form to RPN (3)
- Add brackets to the whole expression so the inner set of brackets denotes the first part to be evaluated
- Move each infix operator to the end of their corresponding set of brackets
- Remove the brackets
Convert 7 + 8 x 6 to RPN
(7 + (8 x 6))
(7 + (8 6 x))
(7 (8 6 x) +)
7 8 6 x +
RPN to Infix Form (3)
- Work from left to right to find the first operator, move it one place to the left, and put brackets around the resulting infix expression
- Repeat step 1, treating brackets as one operand, until you’re at the end of the expression
- Remove redundant brackets
Convert 7 8 6 x + to Infix Form
7 (8 x 6) +
(7 + (8 x 6))
7 + 8 x 6
Why is RPN Used (6)
- Simpler for a computer to evaluate
- Simpler to code algorithm
- Do not need brackets to show correct order of evaluation
- Operators appear in the order required for computation
- No need for order of precedence of operators
- No need to backtrack when evaluating
