HackerEarth Blog

Tl:dr- In order; graph theory, linear algebra, number theory, and multi-criteria decision analysis. Game theory, set theory, nonlinearity, computational geometry a bonus.

Let's say you're learning some new algorithms. Your list might look something like the below list[1]. I'll add in brackets the sort of math you learn about by learning the algo if you get lost down the wiki-rabbit-hole. If you want to solve other similar problems, more of that sort of math will help.

1) Graph algorithms [graph theory]: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.

2) Dynamic programming [self-similarity, finite subdivision rules, nonlinear equations]: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.

3) Number theory [Number Theory]: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.

3) Greedy [goal programming, simplex algorithm, multi-criteria decision analysis]: Standard problems such as Activity selection.

4) Search techniques [linear/vector algebra[2]]: Binary search, Ternary search and Meet in the middle.

5) Data structures (Basic) [graph theory]: Stacks, Queues, Trees and Heaps.

6) Data structures (Advanced)[more graph theory]: Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT),…