Algorithms Flashcards
Master’s method
Method of analysis that solves recurrence relations of the form
T(n) = aT(n/b) + f(n)
where
a and b are constants with a >= 1 and b >1
Amortized analysis
Worst case analysis of a sequence of operations rather than an entire algorithm
For example, worst case of a hash table is O(n) but we consider the average sequence of operations, which does not include reallocating memory for the table. This leads us to O(1) in the average case.
Different methods of amortized analysis
Aggregate method - typical analysis on the aggregation of all operations that should be analyzed
Accounting method - Paying for each operation on the data structure used to help perform the operations
Decision trees
Models decisions that the algorithm will take
Example:
Insertion sort
Nodes contain elements that will be compared
Leaves contain an answer (ordered set of elements)
Edges contain decisions (<= or >)
Merge sort
Time complexity
Worst - O(n lg(n))
Average - O(n lg(n))
Best - O(n lg(n))
Space complexity
O(n)
Divide the list into the smallest unit possible, compare adjacent lists until you have original list but sorted.
Heap sort
Time complexity
Worst - O(n lg(n))
Average - O(n lg(n))
Best - O(n lg(n))
Space complexity
O(1)
Iteratively pull out an object based on some attribute (for example, minimum/maximum) and add to the sorted part of the data structure. Do this until the unsorted part contains 0 objects, and the sorted part contains n objects, equal to the original number of elements in the heap.
Binary sort
Time complexity
Worst - O(n)
Average - O(n)
Best - O(n)
Space complexity
O(1)
In-order traversal of a tree. Must be BST.
Bucket sort
Time complexity
Worst - O(n^2)
Average - O(n + k)
Best - O(n + k)
Space complexity
O(n)
Go through the entire n elements, placing them in buckets. In the best case, the buckets are considered sorted and you only need to go through k buckets to get the sorted outcome. Worst case, all elements to go into the same bucket, so you must again go through n elements to get the sorted collection.
Selection sort
Time complexity
Worst - O(n^2)
Average - O(n^2)
Best - O(n^2)
Space complexity
O(1)
Comparison-based, iteratively progress through the the unsorted side of the list until it is empty and the sorted side contains all of the original elements in sorted order.
Bubble sort
Time complexity
Worst - O(n^2)
Average - O(n^2)
Best - O(n)
Space complexity
O(1)
Traverse the collection while floating the current object to its sorted position.
Quicksort
Time complexity
Worst - O(n^2)
Average - O(n lg(n))
Best - O(n lg(n))
Space complexity
O(lg(n))
Choose a pivot, move it to the end of the collection. Have 2 pointers, move the left one to the right until you find a value greater than the pivot. Move the right one to the left until you find a value less than the pivot. Swap those elements. Repeat until the bounds of those pointers overlap. Repeat the quicksort on the remaining partition.
What is Single Source Shortest Path (SSSP)?
The shortest path from a selected node to all other nodes.
Shortest path for unweighted graph
BFS, find the single source shortest path from a starting node to all other nodes
O(|E| + |V|)
Shortest path for weighted graph
Floyd-Warshall
Best for negative edge weights
Worst case of O(V^3)
Bellman-Ford
Can have negative edge weights
Worst case of O(VE)
If graph is dense it can devolve into O(V^3)
Dijkstra Can't have negative edge weights Similar to Prim's Greedy Min priority queue - O(V^2) Fibonacci heap - O(E + Vlg(V))
Minimal spanning trees
Prim’s
Greedy
Given a starting node, select the minimum edge that is not in the tree so far. Repeat until all nodes are in the tree. Cannot add an edge that makes a cycle.
Kruskal’s
Sort the edges of the tree
Add the shortest edge to the MST (that does not make a cycle)
Repeat until all vertices are in the tree
