2.3 Algorithms Flashcards
A* algorithm
Approximately finds shortest path between two nodes
Big O notation
A way or classifying algorithms based on their complexity
Breadth first traversal
A method of traversing a graph by using a queue to visit all the neighbours of the current node before doing the same to each of the neighbours until the entire graph has been explored
Depth first traversal
A method of traversing a graph by using a stack to travel as far along one route as possible and then backtracking and doing the same for the remaining routes until the entire graph has been explored
What does Dijkstra’s algorithm use
A priority queue
Space complexity
A measure of the amount of memory space needed by an algorithms to solve a particular problem of a given input size
Time complexity
A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size
Constant time complexity O(1)
Time taken is independent from number of elements inputted
Exponential O(2^n)
Double with every item added
Polynomial time complexity O(n^n)
Proportional to elements inputted to the power of n
Processing power and memory
More processing power means time complexity is less important whereas lots of memory means space complexity is less important
What do you do to reduce the space complexity
Perform all of the changes on the original pieces of data
What do you do to reduce time complexity
Reduce number of embedded loops
Best case time complexity for linear search
O(1)
Best case time complexity for BINARY search
O(1)
Best case time complexity for BUBBLE sort
O(n)
How many pointers do stacks use
1 for the top of the stack
What is the top pointer of a stack initialised as
-1
Why is the top pointer of a stack initialised as -1
When empty, value of 0 would suggest there is an element in the stack
Check size of a stack
size()
check if a stack is empty
isEmpty()
Return top element of stack but do not remove
peek()
Add to stack
push(element)
Remove top element of stack and return removed element
pop()
Check size of queue
size()
Check if queue is empty
isEmpty()
return front element of queue but do not remove
peek()
remove front element from queue and return removed element
dequeue()
How can next node be accessed in a linked list
N.next
First item of linked list
Head
Last item of linked list
tail
Best case time complexity for insertion sort
O(n)
Worst case for every space complexity
0(1)
Average and worst time case for linear search
O(n)
Average and worst time case for binary search
0(log(n))
Average and worst time case for bubble sort
O(n^2)
Average and worst time case for insertion sort
O(n^2)
How is dijkstras algorithm implemented
Priority queue
Example of when dijstras algorithm can be used
determine the optimal route to
use when forwarding packets through a network.
