4.3 Algorithms Flashcards
Name an application of breadth-first search
Finding the shortest path for an unweighted graph
Name an application of depth-first search
Navigating a maze
2 differences between depth-first traversal and breadth-first traversal
DF: Chooses to explore the most recent node to be discovered
BF: Chooses to explore the least recent node to be discovered
DF: Implemented using a stack (when implemented iteratively)
BF: Implemented using a queue (when implemented iteratively)
Depth-first traversal algorithm (beyond spec)
Each node has a binary flag discovered
which is updated whenever we pop a node off the stack and consider its neighbours
- Add the start node to the stack and mark it as
discovered
- If the stack is empty, we’re done. Otherwise, pop the top node and visit it
- Push each of the current node’s undiscovered neighbours to the stack, and mark them as
discovered
- Go back to step 2
Breadth-first traversal algorithm (beyond spec)
Each node has a binary flag discovered
which is updated whenever we dequeue an item and consider its neighbours
- Add the start node to the queue and mark it as
discovered
- If the queue is empty, we’re done. Otherwise, dequeue the front node and visit it
- Enqueue each of the current node’s undiscovered neighbours to the queue, and mark them as
discovered
- Go back to step 2
What is tree traversal?
Visiting the nodes of a tree in a specific order
Use of pre-order traversal
Copying a tree
2 uses of in-order traversal
- Outputting the contents of a binary search tree in ascending order
- Producing infix expression from an expression tree
2 uses of post-order traversal
- Infix to RPN conversions
- Producing a postfix (RPN) expression from an expression tree
Pre-order traversal operation
- Visit the node
- Traverse the left hand sub tree
- Traverse the right hand sub tree
In-order traversal operation
- Traverse the left hand sub tree
- Visit the node
- Traverse the right hand sub tree
Post-order traversal operation
- Traverse the left hand sub tree
- Traverse the right hand sub tree
- Visit the node
3 advantages of RPN
- Eliminates need for brackets in sub-expressions
- There is no need for precedence of operators
- The expressions are in a from suitable for evaluation using a stack, as the expression can be evaluated from left to right
Steps for converting postfix to infix (2*)
- Convert “num num op” triplets one at a time, adding brackets each time
- Remove any unnecessary brackets
Steps for converting infix to postfix (3•)
- Add brackets around every operation
- Draw arrow from operator to end of its bracket
- Write expression, keeping numbers in the same order