Algorithms Flashcards
Lomuto’s
- start with s at pivot and i at s+1
- when item is smaller than pivot, increment s and then swap s with i
QuickSort
if(left < right):
split = partition
sort left half and right half
ways to improve QuickSort
- better pivot selection
- do insertion sort on smaller sets
- eliminate recursion
selection (find nth biggest value)
- sort set
- find nth value
quickselect (find nth biggest value)
- choose pivot
- partition & place pivot
- if n < pivot, search in left half
- if n > pivot, seach in right half
- else, you found it!
Master Theorem
T(n) = aT(n/b) + n^d
a < b^d: theta (n^d)
a = b^d: theta (n^d logn)
a > b^d: theta (n^(logb (a) ) )
Closest Pair
- sort points by x coordinate
- divide set into left and right halves on graph
- find the closest pair in each half & assign the smaller distance to D
- put points on within either side of the vertical line by a distance of D in a separate array
- sort this array by y coordinates
- for each point, consider only pairs that are within D distance away from each other
- find the closest pair in this set and set its distance to D’
- the closest pair is one of the minimum between D and D’
Generic Graph Search
- mark source as explored, all others unexplored
- while there is an edge (v, w) with v explored & w unexplored:
- choose some edge w (in an alg specific way, depending)
- mark w as explored
Proof of GraphGenericSearch
What is BFS (Breadth-First Search)?
looks at a graph in layers. layer 0 is the root, layer 1 has the neighbors of the root, layer 2 has the neighbors of the neighbors, etc.
- best used for shortest path distances
How to implement BFS in linear time (O(n)) using a queue?
- mark the source explored, initialize Q
- while Q is not empty:
- remove the vertex from the front of the queue and call it v
- for each edge (v, w) in v’s adj list:
- if w is unexplored, then add it to the end of Q and mark it explored
What is a Queue?
First in - first out DS
What is Depth-First Search (DFS)?
go as deep as you can and only backtrack when necessary
- special case of generic graph search
How to implement DFS in linear time (O(n)) using recursion?
- mark source explored
- for each edge in S’s adj list, if V is unexplored, then DFS (G, V)
How to implement DFS in linear time (O(n)) using a stack?
- mark all vertices unexplored, initialize a stack
- while S is not empty:
- pop V from front of S
- if V is unexplored, then mark it explored. for each edge in v’s adj list, push W to the front of S
What is a Stack?
Last in - first out DS
What is topological sort?
an ordering that follows the directions in a directed graph
- can only occur in graphs that do not have directed cycles
How to use DFS to compute topological sort of a directed acyclic graph?
- mark all vertices explored
- curlabl
What is a strongly connected component (scc)?
A maximum subset of vertices such that there is a directed path from any vertex to any other vertex in the subset
How to use DFS to compute the strongest connected components of a directed graph?
Kosaraju’s algorithm:
1. Grev = graph with directions reversed
2. Call DFS on each V of Grev to find position f(v) for V
3. Call DFS on each V of G from highest to lowest f(v)
Kosaraju pseudocode
- First pass of DFS computes f(v): TopoSort(Grev)
- Second pass of DFS finds SCC in reverse topological order
Mark all V unexplored, #scc = 0
For each vertex, in increasing order of f(v):
If V not explored, then SCC++ & DFSSCC (G,v)
2 basic operations of heaps
- Insert into heap
- Extract min (value with smallest key)
When to use a heap?
When application requires fast min or max computations on a dynamically changing set
Heapsort
- Insert all items into heap
- Extract min n # of times
Dijkstra’s
- initialize a table with source = 0, everything else = ∞
- for the node of focus, update the adj nodes with their cost. if sum thus far + weight < previously assigned weight, change it. otherwise dont.
- pick the smallest value node
- continue
Prove Dijkstra’s
see image
Scheduling Problem: specifies the order in which to do certain jobs for fastest completion time
total time = work(sum of times before it) + work …. and so on
What to do when there are 2 attributes in greedy algorithms?
check if differences or ratios work better
cut and paste technique
the optimal solution is made up of optimal subsolutions
steps to the cut and paste proof
- lets assume the algorithm is not optimal
- then lets replace the suboptimal subsolutions with optimal* ones
- by assumption, the solutions is already comprised of optimal solutions.
- therefore the algorithm must be optimal
memoization
- fill in the table
- traceback
Prim’s
- choose a source
- follow 3 - 4 until done
- identify fringe vertices
- choose minimum out of those and add it to MST if it DOES NOT form a cycle
- return & exit
kruskals
- sort edges in increasing weight order
- keep picking smallest edge while cycle is not created
