My personal collection of algorithms, data structures, and design patterns in C++, Python, and more.

• f[j] = f[j] || f[j-v[i]]
• f[i][j] = max(f[i-1]j-v[i]] + w[i], f[i-1][j])
• f[i,j] = f[i-1,j-a[i]] or f[i-1,j+a[i]]

• f[i,j] = max(f[i,j], f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p[fb[i]]+v[fa[i]]*p[fa[i]])

• f[i] = max{ f[j] } + 1, a[j] < a[i], f[i] ascending, lower_bound

• f[i] = max{f[j] + 1}
• f[i] = min{{f(i-k)} (not stone[i]) {f(i-k)} + 1} (stone[i]);

• f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j - 1]) + 1;

• buy[i] = max(rest[i-1] - price, buy[i-1])
• sell[i] = max(buy[i-1] + price, sell[i-1])
• rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

• uniquePath: C(m+n-2, max(m-1, n-1))
• maxRegionsByALine: n * (n + 1) / 2 + 1
• maxRegionsByAPolyLine: (n - 1)_(2 _ n - 1) + 2 * n
• countTrianglesOfPolygon: C(2 * n - 2, n - 1)

• GCD: Greatest Common Divisor; Extended: gcd(a, b) = a _ x + b _ y
• LCM: Lowest Common Multiple
• Modular exponentiation: (a ^ b) % n
• Modular multiplication (x * y) % n
• mod equation solver: a * x = b % n
• Chinese remainder theorem

• Miller¨CRabin primality test
• Euler's totient function
• Count primes

• Shuffle: scan and swap a[i] with a[random(i, n - 1)].

• Time: O(N), scan and swap a[i] with a[random(i,n-1)].

• Random variables, union, joint distribution, conditional probabilities, chain rule, marginalization, Baye's Rule
• P(A|B) = P(B|A) * P(A) / P(B)
• P(AB) = P(A|B)P(B)
• P(ABC) = P(A,B | C) P(C) = P(A|BC)P(BC) = P(A|BC) P(B|C) P(C)
• rand(0,1): unifiorm
• Y~ uniform (0,1)
• X = Y_1 .. Y_n i.i.d. ~ Gaussian(0,1)
• X = rand(0,1) + rand(0,1) + rand(0,1) + rand(0,1) + rand(0,1)......(100000 times)

• Compute the CDF of the 1D distribution
• Derive the inverse of the CDF
• Map a random variable through the inverse from the previous step.

• Dijkstra: O(E + V log V), heap for pending vertices.
• Bellman Ford: O(VE)
• Kruskal: O(E log V)
• Prim: O(E + V log V) Fibonacci heap and adjacency list

• Graham, BFS for sparse biparate graph ** O(VE)
• Hopcroft-Carp ** O(V^0.5 E)
• Kuhn Munkras ** O(VE^2)
• Max Flow = Min Cut = minimum set to remove for cutting the graph ** O(N^3)
• Dinic ** O(V^2 E)
• HLPP ** O(V^3)
• MinCostMaxFlow ** SPFA << O(VEf)

• Heap

• O(n + m)

• Avereage: O(N), Worst: O(MN)

• When N < 16, use insersion sort, since the data is mostly sorted
• When depth > T, use heap sort
• Time: O(N log N)

• Time: O(N log N)

• Queue

• Stack

• lower_bound, greater or equal to

• Sort and merge

• Reverse (between): Use a dummy pointer
• Deep copy: Copy one after one

• Sliding window
• Moving average

• Calculator

• Time: O(alpha), typically alpha < 4

• multithreading safe singleton
• a static instance member pointing to its self
• all other members are ensured singleton
• garbage collection when destroyed

• create and recycle objects

• virtual factories for creating products