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
Steps for linear search on a list
- Start at beginning of list
- Compare each item to one you want until
- you find it or
- you reach the end of the list
(use an indefinite while loop!)
Steps for binary search on a value X (in English)
- Look at item in centre of sorted list (or array) (sort first if needed)
- If it isn’t X…
2.1. If it is larger than X, you can ignore all of the items above
2.2. If it is smaller than X, you can ignore all of the items below - Check middle of halved list and repeat, until you find X or the sublist cannot be halved any more.
What is the while condition when coding binary search?
lower<= upper && !found
What does it mean if you reach a leaf node before you find X in a binary tree search?
X is not in the tree
Why is space complexity important to consider when analysing binary tree search?
Because the algorithm is recursive, it places a demand on the call stack
Bubble sort (ascending order) pseudocode on array A
N ← length(A)swapped ← Truewhile swapped and N > 1:
__swapped ← False
__for position = 0, 1, ... , N-2:
____if A[position] > A[position+1]:
______swap( A[position] , A[position+1])
______swapped ← True
__N ← N-1
Merge sort complexity
O(n log n)
What is an algorithm?
A sequence of unambiguous steps that can be followed to complete a task and that always terminates
2 reasons why smaller time complexity is better
- A quicker program could solve more of the same problem or run more programs in the same time period
- Computers consume electricity to run…
2 reasons why is smaller space complexity better
- A program that uses less memory could run off cheaper hardware (as less RAM is needed)
- Or a greater number of different algorithms can run on the same hardware simultaneously
What is the purpose of Dijkstras algorithm?
Can the graph be directed/weighted?
- Calculates the shortest path between a node and all other nodes in a graph
- Graph may be directed or undirected
- Graph must be weighted
What approach does merge sort take to sort a list?
Divide and conquer
What is bubble sort’s time complexity? Why?
O(n^2). Since it involves a for loop within a for loop. You need to do n passes of the list/array, and each pass involves swapping all the way down the list.
