Hello, I have just started preparing for the IOI. Apart from learning the C++ language and solving basic problems, I have been looking at the necessary algorithms and data structures to do well (get a medal) at the International Olympiad of Informatics.
I have provided a list below of all the algorithms/data structures/programming concepts I have found that people say are needed for the IOI, but I was wondering what others would think about it. Which ones should I add? Which ones should I take away? Any and all help is greatly appreciated.
Breadth First Search (BFS)
Depth First Search (DFS)
Shortest Path from source to all vertices Dijkstra
Shortest Path from every vertex to every other vertex Floyd Warshall
Minimum Spanning tree Prim
Minimum Spanning tree Kruskal
Johnson’s algorithm
Articulation Points (or Cut Vertices) in a Graph
Bridges in a graph
Longest Common Subsequence
Longest Increasing Subsequence
Edit Distance
Topological Sort/Quick Sort/Merge Sort/Counting Sort/bucket sort/heap sort/partial sort/bubble sort
selection sort/insertion sort
Minimum Partition
Ways to Cover a Distance
Longest Path In Matrix
Subset Sum Problem
Optimal Strategy for a Game
0-1 Knapsack Problem
Assembly Line Scheduling
Binary Search
Order Statistics
KMP algorithm
Rabin karp
Z’s algorithm
Aho Corasick String Matching
Manacher’s algorithm: Part 1, Part 2 and Part 3
Prime Numbers and Prime Factorization
Primality Test | Set 1 (Introduction and School Method)
Primality Test | Set 2 (Fermat Method)
Primality Test | Set 3 (Miller–Rabin)
Sieve of Eratosthenes
Segmented Sieve
Wilson’s Theorem
Prime Factorisation
Pollard’s rho algorithm
Basic and Extended Euclidean algorithms
Euler’s Totient Function
Modular Exponentiation
Modular Multiplicative Inverse
Chinese remainder theorem Introduction
Chinese remainder theorem and Modulo Inverse Implementation
nCr%m and this.
Counting Inversions
Counting Inversions using BIT
logarithmic exponentiation
Square root of an integer
Heavy light Decomposition
Matrix Rank
Gaussian Elimination to Solve Linear Equations
Hungarian algorithm
Link cut
Mo’s algorithm and this
Factorial of a large number in C++
Russian Peasant Multiplication
Catalan Number
Convex Hull
Graham Scan
Line Intersection
Interval Tree
Matrix Exponentiation and this
Maxflow Ford Furkerson Algo and Edmond Karp Implementation
Min cut
Stable Marriage Problem
Hopcroft–Karp Algorithm for Maximum Matching
Dinic’s algo and e-maxx
Binary Indexed Tree or Fenwick tree
Segment Tree (RMQ, Range Sum and Lazy Propagation)
K-D tree (See insert, minimum and delete)
Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
Tries
Suffix array (this, this and this)
Sparse table
Suffix automata
LCA and RMQ
Bit manipulation
linked lists/treaps/skip lists/heap/hash table/tries
recursion
number theory
combinatorics
probability theory
basic string manipulation
memoization
Heuristic algorithms
matrix recurrence
ternary search
fourier transform/fast fourier transform
bellman-ford
bipartite matching algorithms (and bipartite check)
sweep line algorithm
LCP
suffix tree
numerical integration/differentiation
line clipping
ad hoc
M Lucas’s Theorem
hashing
binary experimentation
regular expression
greedy algorithms
travelling salesman
backtracking algorithms
brute force
flood fill
linear search
line intersection
strongly connected components
graph algorithms
reduction (transform and conquer)
radix sort
red-black trees
quickselect
interpolation search
*Understand run-time proof, analysis proof, and correctness proof of all algorithms and data structures