×

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

 32 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 answered 24 Jul '13, 13:39 5★n2n_ 1.8k●6●13●19 accept rate: 9%
 20 A very useful link ,list in-dept analysis of basic to advanced algorithm ,many which are listed above ,very helpful read http://e-maxx.ru/algo/ though in russian but google translator might help. :) answered 27 Jul '13, 03:48 2★johri21 446●1●3●7 accept rate: 12%
 14 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. answered 24 Jul '13, 13:45 8.7k●19●48●98 accept rate: 9%
 14 Hello, I can add a few more topics: Suffix Arrays; LCP; Heuristic Algorithms; Gaussian Elimination; Numerical Integration/Differentiation; Line Clipping; Advanced Maths Ad-Hoc problems; 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 answered 24 Jul '13, 14:23 3★kuruma 17.7k●72●143●209 accept rate: 8%
 10 Hello @all and especially @admin, 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 :D What do you think? Best regards, Bruno answered 12 Aug '13, 16:39 3★kuruma 17.7k●72●143●209 accept rate: 8% 1 Great job! (14 Aug '13, 11:34) tyrant2★ We still have much more to do :D And me, personally, I have way much more to learn :p (14 Aug '13, 15:20) kuruma3★
 10 This website can also of great help in learning basic algorithms: http://www.learnalgorithms.in/ answered 14 Aug '13, 10:37 320●3●4●7 accept rate: 0%
 8 http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html i've found it very useful answered 13 Aug '13, 06:20 2★akrai48 180●2●3●7 accept rate: 0%
 8 I'd suggest further adding Heavy Light decomposition in trees Inverse Modulo operations Lucas theorem method for nCr Pollard Rho Integer Factorization Catalan Numbers Some useful resources : come on code on Some cool problems : Nikhil Garg's blog on quora answered 14 Aug '13, 10:16 1.1k●13●22●29 accept rate: 0%
 2 Tutorial on disjoint set and union find with supporting heuristics. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure answered 14 Jul '14, 13:01 26●1 accept rate: 0%
 1 Levenshtein distance algorithm answered 24 Oct '14, 04:52 2.0k●2●14●32 accept rate: 20%
 1 > 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. answered 24 Oct '14, 05:19 7★xellos0 5.9k●5●42●92 accept rate: 10%
 0 Being a beginner and a little weak at Data Structures particularly from where should I start to get a good grip eventually? answered 26 Oct '15, 03:45 87●2●6 accept rate: 0%
 0 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. answered 26 Oct '15, 13:51 2★wiseboy 129●1●10 accept rate: 0%
 0 sieve of eratosthenes and segmented sieve answered 29 Nov '16, 21:37 164●9 accept rate: 4%
 0 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. answered 30 Nov '16, 12:38 2.6k●1●9●32 accept rate: 7%
 0 Centroid Decomposition of Tree answered 30 Nov '16, 12:58 36●5 accept rate: 14%
 0 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 :). answered 13 Apr '17, 17:43 61●5 accept rate: 0%
 0 "Sorry You don't have enough reputation to upvote" How to get reputations :'( ?? answered 07 Jun '17, 05:33 1 accept rate: 0% Google "Codechefs new karma system" and go through the list. (07 Jun '17, 10:13)
 0 Hey guys have a look at this blog :::: Important Data Structures and Algorithms answered 07 Jun '17, 07:23 318●1●10 accept rate: 1%
 0 You can refer to this link. http://www.geeksforgeeks.org/fundamentals-of-algorithms/ answered 07 Jun '17, 11:32 4★kaush1 1 accept rate: 0%
 0 you can refer this link https://github.com/vicky002/AlgoWiki answered 25 Sep '17, 22:25 41●4 accept rate: 5%
 0 nice work. really helpful ^-^ answered 19 Nov '18, 20:32 118●6 accept rate: 7%
 0 nice work. really helpful ^-^ answered 19 Nov '18, 20:33 118●6 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,657

question asked: 24 Jul '13, 13:02

question was seen: 58,365 times

last updated: 19 Nov '18, 20:33