algorithms

Algorithms

Some common problems and famous algorithms used in coding competitions 😄!

For more details about a specific algorithm follow the links in the tables below.

Sometimes multiple implementations can be available, so the complexity and additional memory available in the table are from the algorithm with the best efficiency.

Graphs

Name	Simple Description	Complexity	Additional Memory
BFS	Shortest Path between a node and all others.	O(E + V)	O(V)
DFS	Simple algorithm to walk in a graph.	O(E + V)	O(V)
Maximum Flow	Multiple implementations for Max. Flow.	TODO	TODO
Kruskal	Find Minimum Spanning Tree in a graph.	TODO	TODO
Lowest Common Ancestor	Lowest common ancestor of a node.	TODO	TODO
Max. match in bipartite graph	Maximum match in a bipartite graph.	TODO	TODO
TopologicalSort	Find "execution" order in a direct graph.	O(E + V)	O(V)

Dynamic Programming

Name	Simple Description	Complexity	Additional Memory
LCS	Longest common subsequence.	O(N * M)	O(N * M)
LIS	Longest increasing sequence.	O(N * M)	O(N * M)
Travelling Salesman Problem	Travelling Salesman Problem (NP-Hard).	TODO	TODO
String Distance	Find the min. changes to make 2 strings equal	TODO	TODO
Knapsack Problem	Knapsack Problem.	O(C * N)	O(C * N)
Min. steps to 1	A good initial problem for beginners.	TODO	TODO

Math

Name	Simple Description	Complexity	Additional Memory
Base Converstion	Longest common subsequence.	TODO	TODO
Fast exponentiation	Fast Exponentiation.	O(logN)	O(logN)
GCD and LCM	GCD and LCM.	log(x, y)	log(x, y)
Extended Euclidean	a * x + b * y = GCD(a, b).	TODO	TODO

Data Structure

Name	Simple Description	Complexity	Additional Memory
BIT	Binay Indexed Tree; range manipulation in arrays.	TODO	TODO
SQRT Decomposition	Range manipulation in arrays (simpler).	TODO	TODO
SegTree	Segment Tree; range manipulation in arrays.	TODO	TODO
SegTree 2D	Segment Tree 2D; range manipulation in arrays.	TODO	TODO
SegTree + Lazy propagation	Segment Tree + lazy propagation.	TODO	TODO
UnionSet	Union Set.	TODO	TODO
Bitmask	Bitmask.	TODO	TODO
SQRT Decomposition	Range manipulation in arrays (simpler).	TODO	TODO

Geometry

Only a file containing a lot of computational geometry code (for now).

Strings

Name	Simple Description	Complexity	Additional Memory
Hash	Hash.	TODO	TODO
KMP	Searches for string W within a main string S.	TODO	TODO
SufixArray	Sorted array with all suffixes of a string.	TODO	TODO
Trie	Ordered tree that stores a dyn.set / assoc array.	TODO	TODO