A comprehensive algorithms review, summarizing the key topics: divide and conquer, graph algorithms, dynamic programming, linear programming, P vs NP, reductions, and more.

Divide and Conquer

Master theorem:

for some constants (a>0) , (b>1) ,and (d ≥0) , then

d is the exponent of the time complexity of the non-recursive part (i.e., the work done outside each recursive call).

Proof: analyze the total work in the recursion tree

FFT

Graph Algorithms

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14

EXPLORE(G, v):  
1. visited[v] = true  
2. pre[v] = clock; clock++      # record discovery time  
3. for each edge (v, u) ∈ E:  
4.    if not visited[u]:  
5.        EXPLORE(G, u)  
6. post[v] = clock; clock++     # record finish time  

DFS(G):  
1. for all v ∈ V: visited[v] = false  
2. clock = 0  
3. for all v ∈ V:  
4.    if not visited[v]:  
5.        EXPLORE(G, v)  

running time: O(|V|+|E|)

SCC (Strongly Connected Components)

1
2
3
4
5
6
7
8
9
10
11
12
13

Input: directed graph G = (V, E)
Output: G's strongly connected components
1. DFS(G)  # run DFS, recording each node's post time
2. by decreasing post time, sort V
3. G' = G transposed (all edges reversed)
4. visited = false for all v ∈ V
5. for each v in V (in decreasing post time):
6.    if not visited[v]:
7.        SCC = {}  # current strongly connected component
8.        EXPLORE(G', v)  # explore the transposed graph with DFS
9.        for each u in SCC:
10.           visited[u] = true  # mark as visited
11.           print(u)  # output the nodes of the current SCC

running time: O(|V|+|E|)

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14

**Input**: graph G, edge weights ℓ, source s  
**Output**: shortest distance from s to every node, dist[]  

1. for each u ∈ V:  
2.    dist[u] = ∞; prev[u] = nil  
3. dist[s] = 0  
4. H = priority queue (key=dist)   # initially contains all nodes  
5. while H is not empty:  
6.    u = H.deletemin()     # extract the node with the smallest dist  
7.    for each edge (u, v) ∈ E:  
8.        if dist[v] > dist[u] + ℓ(u, v):  
9.            dist[v] = dist[u] + ℓ(u, v)  
10.           prev[v] = u  
11.           H.decreasekey(v)  # update v's priority in the queue  

Bellman-Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14

**Input**: graph G, edge weights ℓ, source s (no negative cycles)  
**Output**: shortest distances dist[], or report a negative cycle  

1. for each u ∈ V:  
2.    dist[u] = ∞; prev[u] = nil  
3. dist[s] = 0  
4. repeat |V| - 1 times:  
5.    for each edge e = (u, v) ∈ E:  
6.        if dist[v] > dist[u] + ℓ(u, v):  
7.            dist[v] = dist[u] + ℓ(u, v)  
8.            prev[v] = u  
9. for each edge e = (u, v) ∈ E:  
10.   if dist[v] > dist[u] + ℓ(u, v):  
11.       return "negative cycle exists"  

running time: O(|V| * |E|)

Shortest Paths in a DAG

A topological order is a linear ordering of the vertices of a directed acyclic graph (DAG) in which, for every edge (u, v), u comes before v.

1
2
3
4
5
6
7
8
9
10
11
12

Input: DAG G, edge weights ℓ, source s  
Output: shortest distances dist[]  

1. for each u ∈ V:  
2.    dist[u] = ∞; prev[u] = nil  
3. dist[s] = 0  
4. L = topological_sort(G)   # arrange nodes in linear order  
5. for each u ∈ L (processed in order):  
6.    for each edge (u, v) ∈ E:  
7.        if dist[v] > dist[u] + ℓ(u, v):  
8.            dist[v] = dist[u] + ℓ(u, v)  
9.            prev[v] = u  

running time: O(|V| + |E|)

MST (Minimum Spanning Tree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Kruskal(G)
// Input: undirected graph G = (V, E)
// Output: minimum spanning tree T
1. T = ∅  // initialize the MST
2. for each edge (u, v) ∈ E in increasing order of weight:
3.    if u and v are in different components:
4.        T = T ∪ {(u, v)}  // add the edge to the MST
5.        union(u, v)  // merge the connected components of u and v

Prim(G, s)
// Input: undirected graph G = (V, E), source s
// Output: minimum spanning tree T
1. T = ∅  // initialize the MST
2. for each vertex v ∈ V: dist[v] = ∞; prev[v] = nil
3. dist[s] = 0  // distance from the source to itself is 0
4. H = priority queue (key=dist)  // initialize the priority queue
5. while H is not empty:
6.    u = H.deletemin()  // extract the node with the smallest distance
7.    for each edge (u, v) ∈ E:
8.        if dist[v] > ℓ(u, v):  // if a lighter edge is found
9.            dist[v] = ℓ(u, v)  // update the distance
10.           prev[v] = u  // update the predecessor
11.           H.decreasekey(v)  // update its priority in the queue

Cut property: for any cut (S, V-S) of a graph G, the minimum-weight edge crossing between S and V-S must belong to some MST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Union-Find (disjoint sets)

# initialize a singleton set  
makeset(x):  
1. π[x] = x      # parent pointer  
2. rank[x] = 0   # rank  

# find the root (with path compression)  
find(x):  
1. if x ≠ π[x]:  
2.   π[x] = find(π[x])  # recursively compress the path  
3. return π[x]  

# merge sets (union by rank)  
union(x,y):  
1. rx = find(x), ry = find(y)  
2. if rx == ry: return  
3. if rank[rx] > rank[ry]:  
4.   π[ry] = rx  
5. else:  
6.   π[rx] = ry  
7.   if rank[rx] == rank[ry]:  
8.     rank[ry]++  

Dynamic Programming

Dynamic Programming

• Core idea: break the problem into overlapping subproblems and store the subproblem solutions to avoid redundant computation.
• Key steps:
  1. Define the subproblems
  2. Set up the recurrence (state transition equation)
  3. Determine the evaluation order (bottom-up or memoized search)
• Applications:
  • Longest Increasing Subsequence (LIS): length of the LIS ending at j $L(j) = 1 + \max\{L(i) \mid i < j, a_i < a_j\}$
  • Edit distance: the minimum cost of aligning two strings, $E(i,j) = \min\{1+E(i-1,j), 1+E(i,j-1), \text{diff}(i,j)+E(i-1,j-1)\}$
  • Knapsack:
    • Knapsack with repetition: $K(w) = \max_{i} \{K(w - w_i) + v_i\}$
    • 0/1 knapsack: $K(w,j) = \max \{K(w-w_j, j-1) + v_j, K(w, j-1)\}$
  • Matrix chain multiplication: minimize the number of multiplications, $C(i,j) = \min_{k} \{C(i,k) + C(k+1,j) + m_{i-1}m_k m_j\}$
  • Traveling Salesman Problem (TSP): C(S,j) is the shortest path that passes through the set S and ends at j; complexity O(n^2 2^n).
  • Independent set on a tree: maximum independent set size $l(u) = \max \{1 + \sum \text{grandchildren } l(w), \sum \text{children } l(w) \}$

LIS (Longest Increasing Subsequence)

1
2
3
4
5
6
7
8
9

Input: sequence a[1..n]  
Output: LIS length  

1. for j = 1 to n:  
2.   L[j] = 1  # initialize the length of the LIS ending at j  
3.   for i = 1 to j-1:  
4.     if a[i] < a[j]:  
5.       L[j] = max(L[j], L[i] + 1)  
6. return max(L)  

running time: O(n^2)

LCS (Longest Common Subsequence)

1
2
3
4
5
6
7
8
9
10
11

Input: sequences a[1..n], b[1..m]
Output: LCS length
1. for i = 0 to n: L[i,0] = 0  # initialize the first row
2. for j = 0 to m: L[0,j] = 0  # initialize the first column
3. for i = 1 to n:
4.   for j = 1 to m:
5.     if a[i] == b[j]:
6.       L[i,j] = L[i-1,j-1] + 1  # on a match, extend the length by 1
7.     else:
8.       L[i,j] = max(L[i-1,j], L[i,j-1])  # on a mismatch, take the max
9. return L[n,m]  # return the LCS length

running time: O(n*m)

0/1 Knapsack

1
2
3
4
5
6
7
8
9
10
11

Input: item weights w[1..n], values v[1..n], capacity W  
Output: maximum value  

1. for w = 0 to W: K[w,0] = 0  
2. for j = 1 to n:  
3.   for w = 1 to W:  
4.     if w_j > w:  
5.       K[w,j] = K[w,j-1]  
6.     else:  
7.       K[w,j] = max(K[w-w_j,j-1] + v_j, K[w,j-1])  
8. return K[W,n]  

Linear Programming

MAX Flow

1
2
3
4
5
6
7
8
9
10
11

FORD-FULKERSON(G, s, t):
    for each edge (u,v) in G:
        f(u,v) = 0  // initialize the flow
    while exists path p from s to t in residual graph G_f:
        c_f(p) = min{ c_f(u,v) | (u,v) in p }  // residual capacity of the path
        for each edge (u,v) in p:
            if (u,v) is forward edge:
                f(u,v) += c_f(p)
            else:  // (v,u) is a backward edge
                f(v,u) -= c_f(p)  // decrease the forward flow
    return f  // maximum flow

The idea behind Ford-Fulkerson:

• Build the residual graph: residual capacity of a forward edge = c_e - f_e, capacity of a backward edge = f_e
• Iteratively search for augmenting paths: use BFS/DFS to find an s→t path in the residual graph
• Update the flow: push an amount equal to the minimum residual capacity along the path
• Complexity: O(|V|·|E|²)

Max Flow-Min Cut theorem: the maximum flow equals the minimum cut, i.e., in a flow network, the maximum flow from the source to the sink equals the minimum total capacity of the edges cut when the network is split into two parts.

Bipartite matching can be solved by reducing it to max flow: turn the bipartite graph into a flow network, connect the source to the left-side vertices, connect the right-side vertices to the sink, and give every edge capacity 1.

Simplex

Dual LP

P vs NP

Class P:

• Decision problems that can be solved by a polynomial-time algorithm
• Time complexity O(n^k), where k is a constant

Class NP:

• Decision problems for which, given a solution, its correctness can be verified in polynomial time
• Nondeterministic Polynomial time

NP-Complete problems:

• Problems that belong to NP
• Every problem in NP can be reduced to them in polynomial time
• If any NP-Complete problem has a polynomial-time algorithm, then P = NP

NP-Complete

Search Problem: given an instance I and a solution checker C(I,S) (polynomial-time verification), find a solution S

Search problems are equivalent to NP problems.

Reductions

A -> B (A is no harder than B, A <= B)

Key points:

• Instance transformation
• Solution transformation (including passing along “no solution”)
• Both done in polynomial time

For non-search problems, only the instance transformation is needed.

Reduction chain analysis: 3SAT → INDEPENDENT SET → VERTEX COVER → CLIQUE

1. 3SAT → INDEPENDENT SET

• Goal: reduce Boolean satisfiability (3SAT) to the independent set problem.

• Steps:
  a. Instance transformation:

  • For a 3SAT formula with k clauses, construct a graph G:
    • Each clause becomes a triangle (3 vertices), whose vertices represent the literals in the clause (e.g. $x, \neg y$).
    • Add conflict edges: if two literals are complementary (e.g. x and ), connect them across all triangles.
  • Set the target independent set size g = k (the number of clauses).
    Example: the formula $(x \lor y \lor z) \land (\neg x \lor \neg y)$
    → two triangles: ${x,y,z} \text{ and } {\neg x, \neg y, \text{dummy}}$, and add the edges $(x, \neg x), (y, \neg y)$

  b. Solution transformation:

  • If an independent set of size g exists, then exactly one vertex is chosen from each triangle (the conflict edges guarantee that complementary literals are never both chosen).
  • Set the chosen literals to true (e.g. if x is chosen then x=true; if is chosen then x=false

• Key insight:
  Choosing the independent set = picking one true literal per clause, with a globally consistent assignment.

2. INDEPENDENT SET → VERTEX COVER

• Goal: reduce independent set to the vertex cover problem.

• Steps:
  a. Instance transformation:

  • Given a graph G=(V,E) and independent set target g, use the very same graph G
  • Set the vertex cover target b = |V| - g (e.g. |V|=5, g=2 → b=3

  b. Solution transformation:

  • If a vertex cover C of size b exists, then $V \setminus C$ is an independent set of size g.
    (because C covers every edge → there are no edges inside $V \setminus C$)
  • If an independent set S of size g exists, then $V \setminus S$ is a vertex cover of size b.

• Key insight:
  Independent set and vertex cover are complementary problems: $$S \text{ is an independent set} \iff V \setminus S \text{ is a vertex cover}$$

3. VERTEX COVER → CLIQUE

• Goal: reduce vertex cover to the clique problem.

• Steps:
  a. Instance transformation:

  • Given a graph G=(V,E) and vertex cover target b, construct its complement graph
  • Set the clique target g = |V| - b (e.g. |V|=4, b=1 → g=3

  b. Solution transformation:

  • If has a clique K of size g, then $V \setminus K$ is a vertex cover of G of size b.
    (since K is a complete subgraph in → it has no edges in G → covers every edge of G)
  • If G has a vertex cover C of size b, then is a clique of size g in .

  c. Passing along “no solution”:

  • If has no clique of size g, then G has no vertex cover of size b.

• Key insight:
  The complement of a vertex cover is a clique in the complement graph:

  $$C \text{ is a vertex cover} \iff V \setminus C \text{ is a clique in } \bar{G}$$

Other Algorithms

Euclid’s Algorithm

1
2
3
4
5
6
7
8
9
10
11
12

Euclid(a, b) 
// Input: two integers a and b with a ≥b ≥0
// Output: gcd(a, b)
1. if b = 0 then return a
2. return Euclid(b, a mod b)

extended-Euclid (a, b) 
// Input: two integers a and b with a ≥b ≥0
// Output: gcd(a, b) and integers x and y such that ax + by = gcd(a, b)
1. if b = 0 then return (a, 1, 0)
2. (g, x1, y1) = extended-Euclid(b, a mod b)
3. return (g, y1, x1 - (a / b) * y1)

For any positive integers a and b ,the extended Euclid algorithm returns integers x , y ,and d such that go $d(a, b)=d=a x+b y$

RSA

1
2
3
4
5
6
7
8
9
10
11
12

1. pick large random primes p, q → compute N = p * q
2. choose e such that gcd(e, (p-1)(q-1)) = 1 (coprime)
3. compute d = e⁻¹ mod (p-1)(q-1)  // extended Euclid: ed ≡ 1 mod φ(n)
4. public key = (N, e), private key = d

RSA(n, e, m)
// Input: n = p * q, e, m (plaintext)
// Output: c = m^e mod n

RSA-decrypt(n, d, c)
// Input: n = p * q, d, c
// Output: m = c^d mod n

The correctness of RSA rests on Euler’s theorem:

If gcd(m, n) = 1, then m^φ(n) ≡ 1 (mod n)

Prime Testing

Fermat’s little theorem: if p is prime and a is any integer, then a^(p-1) ≡ 1 (mod p)

1
2
3
4
5
6
7

primality2(N) 
// Input: positive integer N 
// Output: yes/no 
1. Pick positive integers a1, a2, ..., ak<N at random 
2. if ai^{N-1} ≡ 1 (mod N ) for all i=1,2, ..., k 
then return yes 
3. else return no. 

Pr(primality2 returns yes when N is not prime) ≤ 1 / 2^k

Translated from the Chinese original.