Algorithms Flashcards
(30 cards)
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
Ways to store a graph in memory
Adjacency list
List of nodes with each node containing a list of nodes that it is connected to
Adjacency matrix
Matrix of all nodes in the tree. If a node is connected to a given node in its row, place a 1. If not, place a 0.
Proof types
Direct
No further assumptions, just using established facts
Induction
Indirect
Makes assumptions
Contrapositive - if something, then something ([p implies q] if [~q implies ~p])
Contradiction - p^~q implies ~p
Loop invariant
Property of a loop that is true before and after each iteration
Divide and conquer
Divide a large problem into a subset of smaller problems. Solve the smaller problems recursively until the larger problem is solved
Merge sort, binary search
Dynamic programming
Store the results for small subproblems and look them up instead of recomputing. Usually associated with optimization
LCS - what is it and how long
Greedy
Choose best approach based on arbitrary attribute (smallest, biggest, shortest, etc.) Continuously make that choice until problem is solved
Approximation methods
Returns near optimal solutions Vertex cover can be determined with this Example: approximation of 10 with 6 being optimal 10 <= 2*6, yes, that is a 2-approximation
N-approximation
Is your guess within n times the optimal?
Approximation <= n * optimal
DFS
Perform exhaustive search in the forward direction, then backtrack. Do this until every node is visited.
