Fundamentals of Algorithms Flashcards
What is an algorithm?
A set of instructions that completes a task in a finite time and always terminates
What is Graph Traversal?
Visiting each vertex in a graph
Two types of Graph Traversal?
Depth first search and breadth first search
Which traversal is best for navigating a maze?
Depth-first search
What is Breadth-first traversal useful for?
Shortest path on an unweighted graph
What abstract data type is used for breadth-first traversal?
Queue
What abstract data type is used in depth-first traversal
Stack
What types of graphs can be traversed?
Connected graphs
Can a tree undergo depth-first traversal?
Yes, but you might want to use tree-traversal instead
Can a graph traversal start from any node?
Yeah
What is tree-traversal?
Visiting/outputting each node in a tree; it’s an algorithm
Three types of tree-traversal
Preorder, inorder and postorder
Name a use of post-order traversal
- Emptying a tree
- Infix to RPN conversions
- Producing postfix expression from an expression tree
TRICK: Where does the dot go for you to trace the tree for post-order traversal?
To the right
TRICK: Where does the dot go for you to trace the tree for in-order traversal?
Below
TRICK: Where does the dot go for you to trace the tree for pre-order traversal?
To the left
Traversal used for copying a tree?
Pre-order traversal
Name a use of inorder traversal
Output the contents of a binary search tree in ascending order
Can inorder traversal be performed on any tree?
NO! Only binary trees
Can preorder traversal be performed on any tree?
YES!
Can postorder traversal be performed on any tree?
YES!
Where does tree traversal start?
At the root
How do traversals work their way through the tree?
Anti-clockwise
What is true about RPN?
A. Uses queue
B. Eliminates needs for brackets
C. Based on graph
B