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
Convert infix expression to RPN:
14 + 6
14 6 +
Convert infix expression to RPN
(12 - 4) x (3 + 5)
12 4 - 3 5 + x
Convert the following RPN to infix
13 6 + 4 -
(13 + 6) - 4
Convert the following infix expression to RPN
3(4 - 2) + 9
4 2 - 3 x 9 +
Convert the RPN
4 6 7 + - to Infix
4 - (6 + 7)
Which of the following is not an example where reverse Polish is used?
A. PreScript
B. Bytecode
C. PostScript
A
What is the result of this reverse Polish expression?
4 6 8 - -
6
What is the purpose of an optimisation algorithm?
To find the best possible solution to the problem posed
Purpose of Dijkstra’s algorithm?
Find the shortest path between two nodes in a network
Where is Dijkstra’s algorithm used?
Satellite navigation and packet routing
Which is the most time efficient: bubble sort or merge?
Merge sort
Which sorting algorithm is an example of a “divide and conquer” algorithm?
Merge sort
Time complexity of a bubble sort algorithm?
O(n^2)
Time complexity of the merge sort algorithm?
O(nlogn)
