Top three answers for those who don't want to sign up with Quora:
Dynamic Programming appears to account for a plurality (some estimate up to a third) of contest problems. Of course, DP is also not a single algorithm that you can just learn once and retain, so maybe this doesn't answer your question.
I suppose it also depends on whether you consider data structures in the same category as algorithms. There are certainly some data structures that you should be familiar with if you want to do well in programming competitions. The most important ones are range trees (variously known as interval trees or segment trees) and binary indexed trees (BITs), also known as Fenwick trees. Additionally, many DP algorithms make use of a prefix sum array.
The most essential of the single algorithms I can think of are the following, in no particular order. However, you may be disappointed by how rarely some of these actually appear in contests. Most non-DP problems appear to be of the "ad hoc with data structures" variety, and you simply have to practice in order to get good at them.
(To be clear, again, I list below only algorithms that take a single input set, compute some function of it, and carry no state between inputs. This distinguishes them from data structures, which by definition hold state, and categories of algorithms and algorithmic techniques like DP, which don't have some specific function they compute.)
· Sieve of Eratosthenes, or another prime number sieve
· Depth-first search
· Breadth-first search
· Dijkstra's algorithm
· Floyd--Warshall algorithm
· Either Kruskal's or Prim's algorithm
· Some implementation of topological sorting, such as by using DFS
· Convex hull (I recommend the Monotone Chains algorithm)
· Coordinate compression
· Edmonds--Karp, or another implementation of the Ford--Fulkerson method; or a preflow-push algorithm; or, if you are preparing an ACM codebook, Dinic's algorithm. (Note: Max flow is not allowed to appear on the IOI, but may nevertheless appear on national team-selection contests)
· Following are the Algorithms/Concepts that one must know(Especially a programmer) to solve CS puzzles:
· Lists, Arrays, Stack
· Trees- Binary, k-ary, AVL, B and B+ tree
· Sorting and Searching- esp. QuickSort, RadixSort, Binary search and indexing
· Priority Queues- Heaps
· Pattern Matching and Parsing- Regex
· Hashing- Hash Functions
· Disjoint Sets
· Graph Algorithms and Data Structures- Problems like computing the minimum spanning tree, determination of the shortest path between two nodes, matching, and the detection of cut vertexes will arise in a number of situation. Google’s PageRank, for example, is a very concrete application of graph algorithms.
· Dynamic Programming- Closely related to graph algorithms, Dynamic Programming exploit the fact that the optimal solution to a large problem can be expressed as an optimal combination of sub-problems.
· State Space Search Algorithms- limited depth search, · Breadth-first search, A*; Artificial Intelligence; Genetic algorithms
If you want specific algorithms, my top 10 would be:
· Dijkstra's - depending on the type of contest, you might see basic pathfinding problems, or you might see problems with non-obvious reductions to pathfinding problems. Whenever you have a cost minimization problem with a (reasonably small) finite number of states, an initial state a target state, you can look at it as a pathfinding problem.
· Bellman-Ford is useful for pathfinding when edges may have negative costs. For example if you're navigating a maze with potions which boost health and hazards which lower it, Bellman-Ford would be a great approach.
· Floyd-Warshall is useful for computing all paths. It is sometimes used in problems where you don't need all paths, because it's so easy to implement. It is slower than other pathfinding algorithms though, so whether Floyd-Warshall is an option depends on the graph size.
· Edmonds-Karp for max flow/min cut problems. One common application is bipartite matching problems. For example, given N people, M food items, and a list of each person's food allergies, how many people can you feed?
· The Hungarian algorithm for assignment problems. Similar to the above, but in these problems the edges have weights, and we're maximizing the total weight rather than just the number of matchings.
The sweep line "algorithm" (more of a general approach really) is useful for various geometric problems, like the nearest pair problem. Also useful for a variety of intersection-related problems, like finding intersecting line segments, or conflicting calendar events.
· Graham scan or another convex hull algorithm, for problems such as building a minimal fence to enclose animals.
· An algorithm for finding strongly connected components, such as Tarjan's.
· Prim's algorithm for minimum spanning trees.
· Knuth-Morris-Pratt algorithm for string searching.
Other concepts worth studying, which aren't in the above list because they aren't specific algorithms:
· Memoization/dynamic programming is quite useful. Some problems have obvious DP solutions, while others have very non-obvious ones which take practice to recognize.
· Binary search is useful in many optimization problems, so make sure you're very comfortable implementing it.
· Combinatorial game theory comes up now and then. I recommend Thomas Ferguson's introduction.
· Tries are useful in a variety of text-related problems.
Dynamic Programming appears to account for a plurality (some estimate up to a third) of contest problems. Of course, DP is also not a single algorithm that you can just learn once and retain, so maybe this doesn't answer your question.
I suppose it also depends on whether you consider data structures in the same category as algorithms. There are certainly some data structures that you should be familiar with if you want to do well in programming competitions. The most important ones are range trees (variously known as interval trees or segment trees) and binary indexed trees (BITs), also known as Fenwick trees. Additionally, many DP algorithms make use of a prefix sum array.
The most essential of the single algorithms I can think of are the following, in no particular order. However, you may be disappointed by how rarely some of these actually appear in contests. Most non-DP problems appear to be of the "ad hoc with data structures" variety, and you simply have to practice in order to get good at them.
(To be clear, again, I list below only algorithms that take a single input set, compute some function of it, and carry no state between inputs. This distinguishes them from data structures, which by definition hold state, and categories of algorithms and algorithmic techniques like DP, which don't have some specific function they compute.) · Sieve of Eratosthenes, or another prime number sieve · Depth-first search · Breadth-first search · Dijkstra's algorithm · Floyd--Warshall algorithm · Either Kruskal's or Prim's algorithm · Some implementation of topological sorting, such as by using DFS · Convex hull (I recommend the Monotone Chains algorithm) · Coordinate compression · Edmonds--Karp, or another implementation of the Ford--Fulkerson method; or a preflow-push algorithm; or, if you are preparing an ACM codebook, Dinic's algorithm. (Note: Max flow is not allowed to appear on the IOI, but may nevertheless appear on national team-selection contests)