Level 107 Level 109
Level 108

Algorithms


69 words 0 ignored

Ready to learn       Ready to review

Ignore words

Check the boxes below to ignore/unignore words, then click save at the bottom. Ignored words will never appear in any learning session.

All None

Ignore?
n^2
Gale-Shapley Runtime
Breadth-first search Runtime
m+n ; uses queue
Depth-first search Runtime
m+n ; uses stack; cannot be used for finding shortest path!
Dijkstra's Algorithm Runtime
Time: O(|E| |V|log|V|)
Kruskal
Union find data structure. Start with dots and line cheapest edge. Keep adding cheap lines UNLESS creates circuit; O(E log V); or O(m log n) for sorting; uses union find. Better for SPARSE graphs.
Prim's
Start with any node and take the smallest, take the smallest from next node, etc.; O(E + V log V); or O(m log n) with binary heap; uses priority queue; will result in same …
Recurrence
N log n when n>1
O(n)
Merge and Count
minimum edit distance
Time O(mn), Space O(mn), Backtrace O(M+N)
Dijkstra's Algorithm
Probes from starting point, going back to beginning until shortest path found (kind of like breadth first)
Reverse Delete
Start with network. Delete the most expensive links until reach min spanning tree
N log n
Counting Inversions, Sort and Count: Runtime
slower
A is big O of B when A grows
n epsilon
N^epsilon vs long n p , which grows faster?
C^n
which is faster- n^k or c^n
Logn! =
N log N
Floyd-Warshall
Theta(n^3)
n!
Which function is asymptotically greater , 2^n or n! ?
Omega(n!)
Naive Solution to Traveling Salesman
Dynammic Progr Sol to Traveling Salesman
O(n^2 * 2^n) --- Break it down: O(n) [Choices of i] * O(2^n) [choice of s] * O(n) [subproblems]
Belman Ford time and space complexity
Time : O (|V| |E|) or Theta(n^3) Space: O (|V|)
NP
For every X in NP, Y has property X<pY.
What if P=NP?
Then there is an efficient algorithm for all NP problems.
O(nlogn)
Greedy Runtime?
Divide and Conquer Runtime?
O(nlogn); Divide O(1), Sort 2T(n/2), merge O(n)
O(n^2)
Dynamic Programming Runtime?
3 SAT
Is there a satistfying argument?
Brute force: O(2^n); Dynamic Progr: O(n^w)
Knapsack-- is there faster than brute force?
Vertex Cover
Poly only for special class of instances
NP Complete
A problem in NP such that every problem in NP poly reduces to it
NP Hard
A DECISION problem such that NP reduces to it
Hamiltonian cycle
Given an undirected graph G = (V, E), does there exist a simple
Direct Hamiltonian cycle
Ham cycle but digraph (DIR <p HAM)
List 4 NP Problems in order
3 SAT<p Indep Set =p Vertex Cover <p Set Cover
Example certificate: composite
Boolean C(s,t) {
Intractability
Deterministic
Poly time solvability
If there is an algorithm that correctly solves it in O(n^k) time for some constant k
co-NP
complement of decision problem NP (No-Ham, Primes)
Set Cover
Given a set U of elements, a collection S1, S2, ..., Sm of subsets of
Independent Set
Given a graph G = (V, E) and an integer k, is there a subset
VERTEX-COVER ≡P INDEPENDENT-SET.
Let S be any independent set of size k.
3D Matching
Given 3 disjoint sets X, Y, and Z, each of size n and a set
Scheduling with release times
Create n jobs with processing time tj = wj, release time rj = 0,
poly-time certifier.
NP is the set of problems for which there exists a __________.
T(n) = Θ(f(n))
Master Theorem: IF a·f(n/b) = kf(n) for some constant k < 1,
T(n) = Θ(n^logb a)
If a·f(n/b) = Kf(n) for some constant K > 1, then
If a·f(n/b) = f(n),
T(n) = Θ(f(n)logb n)
Flow
∑ƒ(e) -∑ƒ(e) = v(ƒ)
Ford-Fulkerson
O(m n C)
Shortest Path
algorithm runs in O(m^2 n) time, Theta(n^2) space
n-1
A tree on n nodes has how many edges?
MST
Given a connected graph G = (V, E) with realvalued
Yes (cut property)
edge with exactly one endpoint in S. Does the MST contains e? Assume only unique edges.
No (cycle property)
belonging to C. Does the MST contains f? Assume only unique edges.
Cycle-Cut Intersection
A cycle and a cutset intersect in an even number of edges.
Clustering
Like Kruskal's algorithm; Equivalent to finding an MST and deleting the k-1 most expensive edges.
tree, telescoping, induction
Name 3 ways to prove recursion
FFT Algorithm
fft(n, a0,a1,...,an-1) {
n by 3k+3
How to construct a HAM graph with n variables and k clauses?
3 SAT <p HAM
Suppose G has a Hamiltonian cycle !.
Capacity of a cut
cap(A, B) = ∑c(e) e out of A
An s-t flow is a function that satisfies:
! For each e ∈ E: 0 ≤ f (e) ≤ c(e)(capacity)
Weak duality.
Let f be any flow, and let (A, B) be any s-t cut. Then
Max-flow min-cut theorem.
The value of the max flow is equal to the value of the min cut.
Is generic Ford-Fulkerson algorithm polynomial in input size?
No. If max capacity is C, then algorithm can take C iterations
edge-disjoint
Two paths are edge-disjoint if they have no edge in common.
Segmented Dynamic Prog
min { e(i, j) + c + OPT(i -1)} run time: O(n^3), O(n^2) pairs, O(n) per pair using previous formula.
Knapsack
max OPT(i -1, w), v i + OPT(i -1, w-w { i )} otherwise
Detecting Negative Cycles
Can detect negative cost cycle in O(mn) time. O(m + n) space.