4.3 Algorithms Flashcards
Graph Traversal (definition)
visiting all the nodes on the graph
Example of:
- Breadth First Search
- Depth First Search
- Breadth First: shortest path for an unweighted graph
- Depth First: navigating a maze
Breadth First Search Process (5)
- enqueue root and add to visited list
- are there any nodes adjacent to the node at the front of the queue that haven’t been visited?
- if so: enqueue node and add to visited list
- if not: dequeue
- repeat process until queue is empty (all nodes have been visited)
Depth First Search Process (5)
- push root node onto stack and add to visited list
- is there a node adjacent to the node at the top of the stack that has not been visited?
- if so: push node onto stack and add to visited list
- is not: pop off stack
- repeat process until stack is empty (all nodes have been visited)
Pre Order: acronym, dot placement
- NLR (node, left , right)
- dot to the left
In Order: acronym, dot placement
- LNR (left, node, right)
- dot underneath
Post Order: acronym, dot placement
- LRN (left, right, node)
- dot to the right
Examples Using Tree Traversal Algorithms
- Post Order: converts infix notation to RPN
- In Order: outputs contents of a binary search tree in ascending order
Convert Infix to RPN: 3 + (4 * 2) - 1
3, 4, 2, *, +, 1, -
Advantages of RPN over Infix Notation (2)
- simpler for a machine to evaluate
- RPN doesn’t require brackets, unlike infix notation
Using a Stack to Evaluate RPN (5)
- if character in expression is a number: push value onto stack
- if character in expression is an operator:
- pop last two values off the stack
- apply the operator to the two values
- push result onto stack
- repeat process until end of expression is reached
- pop top value off stack to give result
Linear Search
- process (2)
- time complexity
- advantage
- iterates through each item in list and compares it to condition element
- only breaks if condition is met or program reaches end of the list
- time complexity: O(n)
- adv: data doesn’t need to be in order
Binary Search
- process (1)
- time complexity
- disadvantage
- when searching, the index of the middle of the set is calculated by adding the leftmost and rightmost indexes and dividing by 2, discarding any remainder
- time complexity: O(log n)
- dis: data needs to be in order
Binary Tree Search
- time complexity
- use
- advantage
- disadvantage
- time complexity: O(log n)
- rapid search of data
- adv: data does not need to be in order
- dis: it takes more memory to store the data (3 times the amount of data)
Bubble Sort
- process (1)
- time complexity
- if swapped is still false at the end of a pass through the data then no swaps were made, which means the data is now in order and the sort can finish
- time complexity: O(n^2)
Merge Sort
- process (2)
- time complexity
- follows a ‘divide and conquer’ approach
- uses a recursive technique
- average time complexity: O(n log n)
Dijkstra’s Algorithm
- process (3)
- examples (2)
- finds the shortest path between a given node and all other nodes (graph must be weighted)
- stores nodes in a priority queue
- rule: the node with smallest distance from start is dequeued
- e.g. use with GPS devices
- e.g. solving a Rubik’s cube
