i <-- items. j <-- capacity.

F(i,j)= max{F (i-1,j), v_i + F(i-1, j-w_i)} if j-w_i ≥ 0

                 F(i-1, j)                                if j-w_i < 0

Yes, ordering matters.

F(0,j)=0 for all j

F(i,0) = 0 for all i

O(mn)

Where m=length of first, n=length of second

max{v_i + F(j-w_i)}

all items wi ≤ j

M(n, k) = Min    {max (M(i, k-1)), ∑ S_j}

           ^{i=1, 2...n-1}

Look at the minimum of the smaller partitions (k-1) and the remaining numbers. The remaining numbers will count as a partition as well, since we want the smallest of the max partitions.

θ(n*w)

n - different items

w - capacity

• Make |V| - 1 extractMin (getting smallest element from queue)
• |E| * changePriority (worst case |V|) operations of a priority queue. But since we use a heap it is |E|log(|v|)

T: MST for G but e' (min cost edge between S and V-S) is not in T.

Since T is a min spanning tree, there must be a unique path between two vertices.

Take T U {e}

 -There is a cycle, so there's an edge e that goes from S to V-S

No cycles.

Minimal set of edges containing all vertices |V| = |E| + 1

T' = (T - {e}) U {e'}

T' is a spanning tree because |V| = |E| + 1

Weight(e') < weight(e)

Total weight(T') < total weight (T)

So T is not the minimal spanning tree

e' must be in MST

1)Prim builds a tree by adding min cost edge to existing tree.

2) Vertices of existing tree = S. Vertices not in existing tree = V-S.

-Adding min cost edge at each step

Any linear programming problem with a nonempty, bounded, feasible region has an optimal solution. Also, optimal solution is always at the extreme point of the region.

O(g(n)): functions f(n) that grow no faster than g(n)

Θ(g(n)): functions f(n) that grow at same rate as g(n)

Ω(g(n)): functions f(n) that grow at least as fast as g(n)

Net flow across cut = v. v = Σ flows on edges from X to V-X - Σ flows on edges from V-X to X.

Second term is not negative, there are no negative flows

Since v =  Σ X → V-X - Σ V-X →X

and c =  Σ X → V-X

Thus v ≤ c

Form a cut with  X being set of vertices reachable from the source in the final iteration of shortest augmenting path. X contains source, not sink. Therefore, X and the complement form a cut.

Each edge (i,j) from X to V-X has unused capacity of 0, otherwise the end vertex j would have ended up in V-X. Each edge (j,i) has flow 0, there are no back edges.

v =  Σ flows on edges from X to V-X - Σ flows on edges from V-X to X.

Bold = 0.

= capacity of the cut. 

r(s_a) = f(s_a) / f(s*) --> minimization

max is flip

A list of vertices in such an order that for every edge in the graph, the vertex where the edge starts is listed before the vertex where the edge ends. (Course Prerequisites Example)

Guesses the random string to solve problem

Checks string correctness in polynomial time

Worst case - Θ(n²)

Average case - Θ(n)

Sorting points by x-coordinate can be done in O(nlogn)

If f(x) and g(x) are functions from Z+ -> Z+. Then f(x) is O(g(x) if there exists _________________________ such that______________________________ 

FOR ALL_____________________________.

A positive constant c and non-negative integer k

such that

f(n) ≤ c g(n)

for every

n ≥ k 

If f(x) and g(x) are functions from Z+ -> Z+. Then f(x) is θ(g(x) if there exists _________________________ such that______________________________ 

FOR ALL_____________________________.

two integers C₁ and C₂ and a k, all greater than 0

such that

C₁g(x) ≤ f(x) ≤ C₂g(x)

for all

n > k

1 ↔ 

2 [image]

3 [image]

4 Z

5 C

6 [image]

7 →

8 [image]

9 [image]

1 Implies and implied by

2 Is an element of

3 Is a subset of

4 The set of integers

5 The set of complex numbers

6 The set of real numbers

7 Implies

8 For all

9 There exists

1) Decide Input Size n

2) Identify Basic Operation

3) Worst/Avg/Best Case of Input size n

4) Sum number of times basic op executed

5) Simplify using standard formulas

Take the left-most x-point and right-most x-point, divide plane with this. 

Divide points on each side of line segment according to the line determined by the point in that subset that is farthest from the existing line.

2j, 2j + 1, floor of j./2.

Parents are in first floor of n/2

Loop until done with root

Observe right to left parents

If it doesn't satisfy heap condition - exchange with largest child until heap condition holds (Drift Down)

(Until heap condition holds means if you exchange, the loop hits the child that resulted)

1) Divide points given into two subsets P₁ and P₂ by a vertical line x=m where m is a number so that the points are equally split

2) Compute d₁ recursively doing closest pair to left side

3) Comput d₂ recursively doing closest pair to right side

4) let d= min(d₁, d₂)

5) S = set of points such that their x-coordinates are within d distance of m 

6) Loop over points in S using Q

7) for each point Γ in S we compute its distance if Γ_y < P_y - d

8) if its distance to P is less than d, d= that distance

return

Directed graph

Acyclic - No cycles