Level 107
Level 109

#### 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.

**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.