Thursday, June 6, 2013

What are 10 algorithms one must know in order to solve most algorithm challenges/puzzles?

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.
  • 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 searchBreadth-first searchA*; Artificial Intelligence; Genetic algorithms

Bipartite matching
Divide and conquer
Dynamic programming
Fast Fourier transforms
Greedy algorithms
Huffman coding
Max cut
Max flow
Median finding
Min cut
Minimum spanning tree
Randomized algorithms
Shortest paths
Strassen's algorithm
Union find

Some quotes from my email communication with some Topcoder top 10 guys five years ago:

  • From my experience, you don't really need to know that many advanced 
    algorithms, not even in the ICPC world finals. It's much more about just 
    realizing which algorithm in your arsenal you should be using on a 
    specific problem, implementation details etc. And the only way to get 
    that practice is to solve many, many problems - like 1000+ or so, just 
    in order to speed up your coding skills, improve the implementation 
    techique (you shouldn't have to think if it's better to do DFS or BFS or 
    DP or memoization on some problem where all these methods might be 
    applicable), and write bug-free code in the first try.
  • What's important is to have a foundation in the basics and be able to adapt those approaches to brand-new problems.  The basics include: various forms of graph searching, max flow, dynamic programming, etc. BTW, I have no idea what the Aho-Corasick and Chu-liu/Edmonds algorithms you mentioend are. :)
  • You may want to learn something about data structures,  sometimes (but rarely) some balanced tree is needed, some times 2 dimensional range tree can be used.

I also have teamed up with some of the strong guys before, I actually couldn't believe how simple their solutions looked like. So, I think its more about practicing and solving problems than learning new algorithms.

  1. Learn how to use a web search engine to determine which general technique is useful for the problem at hand
  2. Learn how to scan TopCoder/Spoj/Codechef forums for similar techniques where you might get more insight about the problem at hand.
  3. Learn how to perform back-of-the-envelope calculations for determining the approximate big-Oh for the solution you have in mind.
  4. Understand how you can augment standard data structures that others have mentioned in this thread to quickly help you do what you want to do. There is a chapter on this in CLRS, which just about skims the surface of what is possible.
  5. Learn about lazy propagation. Mostly useful for tree-based solutions.
  6. Learn how to code exhaustive search (usually done recursively) - since it's useful when all else fails.
  7. Something people (and me) usually miss is trying to use binary search (BS) over the solution space. For example, BS might be useful not just to search for an element in a sorted array, but if you have a Yes/No oracle AND the search space is BS-able, you can guess the answer, and invoke the oracle O(log n) times.
  8. Ternary search is so useful. I hardly ever use it since I'm too old for this, but it's my loss and your gain.
  9. Ask others - this is the easiest algorithm!
  10. Brian Bi has given a super answer and he maintains a very useful wiki at Main Page - PEGWiki. If you Google Search for it, then I am assuming that you see the pages in non-increasing order of their page rank. This might translate to more popular (and hence more searched/linked) pages showing up on top. I would start with everything on pages 1 & 2.
  11. Don't give up. Refer to Point #9.

No comments:

Post a Comment