Unit 12 - Algorithms Flashcards
define big O notation
an approximation of how well an algorithm scales with an increasing data set
two main parts of big o
- time complexity
- memory complexity
description of O(1)
constant
description of O(log n)
logarithmic
description of O(n)
linear
description of O(n log n)
linearithmic
description of O(n^2)
polynomial
description of O(2^n)
exponential
description of O(n!)
factorial
best to worst big O scenarios
O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(2^n)
O(n!)
best, average and worse case scenarios of time complexity for linear search
best - O(1)
average - O(n)
worst - O(n)
best, average and worse case scenarios of time complexity for binary search array
best - O(1)
average - O(log n)
worst - O(log n)
best, average and worse case scenarios of time complexity for binary search tree
best - O(1)
average - O(log n)
worst - O(n)
best, average and worse case scenarios of time complexity for hashing
best - O(1)
average - O(1)
worst - O(n)
best, average and worse case scenarios of time complexity for breadth/depth-first traversal of a graph
best - O(1)
average - O(V + E)
worst - O(v^2)
V = vertices
E = edges
best, average and worse case scenarios of time complexity for bubble sort
best - O(n)
average - O(n^2)
worst - O(n^2)
best, average and worse case scenarios of time complexity for insertion sort
best - O(n)
average - O(n^2)
worst - O(n^2)
best, average and worse case scenarios of time complexity for merge sort
best - O(n log n)
average - O(n log n)
worst - O(n log n)
best, average and worse case scenarios of time complexity for quick sort
best - O(n log n)
average - O(n log n)
worst O(n^2)
space complexity for bubble sort
O(1)
space complexity for insertion sort
O(1)
space complexity for merge sort
O(n)
space complexity for quick sort
O(log n)
what makes a good algorithm
- gives the correct output for any set of valid inputs
- finite number of steps
- accomplish an identifiable task
- must always terminate
- readable code
- minimal memory overhead
- interoperability between algorithms
pseudocode for bubble sort
similarity between linear and binary search
- same best case case time complexity = O(1)
- both find the item being searched for if it is the list
differences between binary and linear search
- different average and worst case time complexities = linear: O(n), binary O(log n)
- binary search must be performed on a sorted list
similarities between bubble and insertion sort
- both sort the list
- same best, average and worst case time complexities - O(n) and O(n^2)
- same space complexity = O(1)
differences between bubble and insertion sort
- in one pass, bubble sort has one item in the correct place where as insertion sort has all items in the correct order
pseudocode for insertion sort
pseudocode for merge sort
*** MAIN PROGRAM *******
def mergeSort(alist):
if len(alist)>1:
print("Splitting ",alist)
mid = len(alist)//2 # performs integer division
lefthalf = alist[:mid] # left half of alist put into lefthalf
print ("left half ",lefthalf)
righthalf = alist[mid:] # right half of alist put into righthalf
print ("right half ",righthalf)
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
endwhile
endif #check if the left half still has elements not merged #if so, add them to alist
while i<len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1 endwhile #check if the right half still has elements not merged #if so, add them to alist
while j<len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1 endwhile
print("Merged sublist ",alist)
endif #ENDSUB
alist = [5, 3, 2, 7, 9, 1, 3, 8]
print(“\nUnsorted list: “,alist)
mergeSort(alist)
print(“\nSorted list: “,alist)
how does a quick sort work
- The algorithm works by finding a split point, which divides the list into two sub lists, one containing items less than the value at the split point, one containing items greater than the value at the split point.
- The first step is to choose a value called the pivot value, typically the first item in the list
- In order to find the split point where the pivot belongs, left and right pointers are used
- The left pointer moves right, until it finds an item larger than the pivot, and then it stops and hands over to the right pointer
- The right pointer moves left until it finds an item smaller than the pivot, and then stops
- The values in each pointer swap.
- The pointers repeat this process until they cross over.
- The pivot value swaps with the right pointer – this value is now in place.
- Each sub list is treated the same way until it is all sorted.
advantages of a quick sort
- extremely fast time complexity O( n log n)
- does not need additional memory like merge sort
disadvantages of a quick sort
- if the split point are not near the middle of the list the division will be uneven = O(n^2)
- if the list is very large and recursion continues too long, it may cause stack overflow and the program will crash
what are the two ways to traverse a graph
- depth first
- breadth first
how does depth-first traversal work
you go as far as you can down a path before backtracking and going down the next path. it uses a stack to keep track of the last node visited, and a list to hold the names of nodes that have been visited – start with both empty
pseudocode for depth-first traversal
applications of depth first traversal
- job-scheduling
- finding a path between two vertices
- solving puzzles such as navigating a maze
how does breadth first traversal work
you explore all neighbours of the current vertex, then the neighbours of each of those vertices and so on. a queue is used to keep track of nodes that we still have to visit.
applications of breadth first traversal
- find the shortest path between two points
- web crawler
- facebook uses it to find all the friends of a given individual
what is depth-first traversal also known as on trees
pre-order traversal
time complexity of a graph with max edges
O(n^2)
what is djikstra’s algorithm used for
designed to find the shortest path between a start node and every other node in a weighted graph
how does djikstra’s algorithm work
- uses a priority queue as the supporting data structure to keep record of which vertex to visit next
- it starts by assigning a temporary distance value to each node
- the temporary distance is 0 at the start node
what are computable problems
if there is an algorithm that can solve every instance of it in a finite number of steps
what are computational problems
theoretically solvable by computer but if they take millions of years to solve, they are in a sense, insolvable
2 limitations of computation
- algorithmic complexity
- hardware
what is an intractable problem
a problem that does not have a polynomial time solution. although they may have a theoretical solution, it is impossible to solve it within a reasonable time for values of n greater than something very small.
big O = O(n!), O(2^n)
what is a tractable problem
a problem that has a polynomial time solution or better = O(n), O(nlogn), O(n^2), O(n^k)
what are heuristic methods
one which tries to find a solution, which may not be perfect but which is adequate for its purpose
how does the A* algorithm work
Two cost functions:
- G(x) - the real cost from the source to the given node
- H(x) - the approximate cost from node(x) to the goal node (heuristic function)
Calculate: f(x) = g(x) + h(x), stipulates that h(x) should NEVER be greater than g(x).
The algorithm focuses only on reaching the goal node, unlike Djikstra’s algorithm which finds the lowest cost or shortest path to every node.
example use for djikstra’s algorithm
example use of A* algorithm
benefits of recursion
- quicker to write – less lines of code
- suited to certain problems - trees
- reduce the size of a problem with each call
- more natural to read
drawbacks of recursion
- can run out of stack space due to too many calls causing it to crash
- more difficult to trace/follow as each frame on the stack has its own set of variables
- requires more memory than the equivalent iterative algorithm
- usually slower
