Unit 8 - Algorithms Flashcards
What is the time complexity for a merge sort?
The time complexity for a merge sort is O(n log n), where log is base 2.
What is the difference between the concepts of depth-first and breadth-first traversals?
A depth-first will go as far down one path as possible before starting a new one, whereas a breadth-first traversal will explore all neighbours of a vertex before moving on.
What are the data structures required for a depth-first traversal?
A depth-first traversal requires a list/array to track the visited nodes and a stack to track which node to analyse.
Outline the process for a depth-first traversal.
1) Pick a starting node to be the current node, add it to visited.
2) Select a neighbour of the current node and add it to visited, setting it as the new current node and adding the previous current node to the stack. If current node has no neighbours, pick the top node of the stack to be the new current node and pop it.
3) Repeat part 2 until stack is empty.
Name the two data structures required for a breadth-first traversal.
A breadth-first traversal requires a list/array to track the visited nodes and a queue to track which node to analyse.
Outline the process for a breadth-first traversal.
1) Pick a starting node and enqueue it.
2) Dequeue from queue and add that node to visited. Enqueue all the neighbours to the dequeued node.
3) If queue isn’t empty, repeat step 2.
What is the definition of a tractable problem?
A tractable problem is one with a solution of polynomial-time or better. Problems that do not satisfy this criteria are intractable.
What is a heuristic approach?
A heuristic approach is one that prioritises getting an adequate solution in a relatively short amount of time instead of getting an optimal solution in a large amount of time. They may sacrifice some accuracy to achieve faster results.
