CS170 Misc. Notes

Duality

Duality is the phenomenon where for any primal LP, there exists a dual LP that are both optimal for the same question. The main idea is for any max LP, we can create a min LP that returns an upper bound for the primal question by introducing a set of non-negative multipliers.

How to find the Dual LP

1. Multiply each constraint by a multiplier, y_i
2. Combine constraints into one inequality
3. Factor out the original x_i variables
4. Use primal objective to write new dual and nonnegativity constraints

Max Flow

Given a directed graph with edge capacity constraints, send as many units of “flow” from the source s to the the sink t. In order to find the max flow, keep sending units of flow through the shortest available path from s to t using BFS.

Using Max Flow to Solve Problems

• For “at most k” constraints, create edges leaving with capacity k.
• If constraint A belongs to only one constraint B, add edge of capacity 1.
• Add edge between constraints that satisfy each other.

Fermat’s Little Theorem

Given a prime number, p, for any integer a:

a^p = a (mod p)
a^p-1 = 1 (mod p)

Miller-Rabin primality test

Given a number p, p is prime if and only if either:

a^d = 1 (mod p)
a^2r*d = -1 (mod p)

is true for any a.