# What are the "must known" algorithms for online programming contests?

Hello all,
I’ve been practicing at Codechef for a while and now I’m gradually moving toward medium/hard problems. However many algorithms at these levels are very difficult to predict, and I was always stuck because I’m not aware of them. So I open this topic, my hope is to have a wish-list of most used algorithm for online programming contest that I can look up for reference. Here is my short-list up to now:

1. Segment tree (with lazy propagation)
2. Interval Tree
3. Binary Indexed Tree
4. Fast Modulo Multiplication (Exponential Squaring)
5. Heuristic Algorithms
6. KMP string searching
7. Manacher’s Algorithm
8. Union Find/Disjoint Set
9. Trie
10. Prime Miller Rabin
11. Matrix Recurrence + Fast Modulo Multiplication for counting
12. Stable Marriage Problem
13. Extended Euclid’s algorithm
14. Ternary Search
15. Fast Fourier Transform for fast polynomial multiplication
16. Djikstra’s algorithm, Bellman-ford algorithm, Floyd-Warshall Algorithm
17. Prim’s Algorithm, Kruskal’s Algorithm
18. RMQ, LCA
19. Flow related algorithms, assignment problem, Hungarian algorithm
20. Bipartite matching algorithms
21. Heavy-light decomposition
22. Sweep line algorithm
23. Z algorithm
24. Convex Hull
25. Suffix Arrays
26. LCP
27. Suffix Tree
28. Gaussian Elimination
29. Numerical Integration/Differentiation
30. Line Clipping
32. Aho–Corasick string matching algorithm;
33. Calculate nCr % M Lucas’s Theorem
34. Heavy Light decomposition in trees
35. Inverse Modulo operations
36. Pollard Rho Integer Factorization
37. Catalan Numbers

174 Likes
• Euclid’s GCD Algorithm
• Extended Euclid’s algorithm
• Binary Search, Ternary Search
• Sieve of Eratosthenes for finding primes
• Fast Fourier Transformation for fast polynomial multiplication
• Graph algorithms - BFS, DFS, finding connected components
• Djikstra’s algorithm, Bellman-ford algorithm, Floyd-Warshall Algorithm
• Prim’s Algorithm, Kruskal’s Algorithm
• RMQ, LCA
• Flow related algorithms, assignment problem, Hungarian algorithm
• Bipartite matching algorithms
• Heavy-light decomposition
• Sweep line algorithm
• Z algorithm
35 Likes
• Kruskal’s or Prim’s algorithm
• Dijkstra’s algorithm
• Convex Hull

Edit: It would be a nice idea to group these algorithms. For example, KMP algortihm, Aho-Corasick algorithm, Rabin-Karp algorithm all fall under the category of String Match, and hence should be put under the category of string match algorithms; and so on for other algorithms as well.

Grouping would help newbies like me to explore a particular group and learn all the algorithms in that.

16 Likes

Hello,

I can add a few more topics:

• Suffix Arrays;
• LCP;
• Heuristic Algorithms;
• Gaussian Elimination;
• Numerical Integration/Differentiation;
• Line Clipping;
• Aho–Corasick string matching algorithm;
• Knuth–Morris–Pratt algorithm;

Sadly, this list is endless and the hardest part is to understand which of these topics need to be applied to solve a given problem.
As a bonus, you can have variations of these standard topics which may require mixing some of these concepts.

I will edit the above post with all these suggestions, except some of the suggestions given by @n2n_, since putting on the same bag, FFT and Sieve of Eratosthenes for finding primes, seems a bit overkill to me, as the second one is a basic algorithm and not needed to advanced problems I would say Best regards,

Bruno

15 Likes

A very useful link ,list in-dept analysis of basic to advanced algorithm ,many which are listed above ,very helpful read MAXimal :: algo though in russian but google translator might help. 24 Likes

Is the idea of linking all of the above topics to some resource with a tutorial and suggested problems still up?

Because if it is, I can try to write about the topic 3. Fast Modulo Multiplication (Exponential Squaring), as it is a topic I master relatively well, and, when I’m finished with my tutorial I can provide the link here What do you think?

Best regards,

Bruno

11 Likes

http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html
i’ve found it very useful

9 Likes

Some useful resources : come on code on

Some cool problems : Nikhil Garg’s blog on quora

8 Likes

This website can also of great help in learning basic algorithms: http://www.learnalgorithms.in/

11 Likes

Tutorial on disjoint set and union find with supporting heuristics.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

2 Likes

Levenshtein distance algorithm

1 Like

> Catalan numbers

Why?

This is not an algorithm. The way they can describe a lot of stuff is nice, but I’ve never ever seen them used in a solution in competitive programming (unless you count “bruteforce the first few numbers and google them in OEIS” an algorithm, which I don’t).

Similarly, anything that contains “ad-hoc” is not an algorithm, practically by definition. “Ad-hoc” means something that doesn’t fall under a well-known algorithmic technique.

6 Likes

Being a beginner and a little weak at Data Structures particularly from where should I start to get a good grip eventually?

There is an “awesome” resource for this and a lot other things. https://github.com/sindresorhus/awesome
Though I don’t remember the original author’s name, this is the best I’ve come across. Be sure to check it out.

1 Like

sieve of eratosthenes and segmented sieve

You can also add data structures as DS + Algo’s = Programs. I suggest adding a few basic data structures which would help. Also you could add topics like DP.

Centroid Decomposition of Tree

Can anyone also mention the approaches that we have to know like Dynamic Programming or any other approaches for programming contests.
Classifying these algorithms based on the approach will also really be beneficial, may be i am asking for more here :).

“Sorry You don’t have enough reputation to upvote” How to get reputations :’( ??

2 Likes

Hey guys have a look at this blog ::::
Important Data Structures and Algorithms