Sunday, 27 November 2016

Which are the 10 algorithms every computer science student must implement at least once in life?

Coming from an intensive programming contest background, having read Introduction to Algorithms, etc., but then moving on to doing real-life projects, I find that some of the more interesting and powerful algorithms in a problem solving setting find little use in the industry.

I'm thus going to present algorithms that carry over to engineering, not just research and TopCoder. Another goal was for these algorithms to be useful and widely applicable hammers in their own right, not just as an idea. The benefits of most "algorithms" will be hard to explain them to someone who has not yet been introduced to them, but I tried my best of giving a hint for their role.

  1. Naive Bayes. Classification is a natural first step to machine learning and the Naive Bayes classifier combines that with the trending concept of Bayesian inference. Despite its simplicity, can address key problems like spam classification.
  2. Map-Reduce. A simple and visual way of leveraging multiple computers to solve a single task. More on its different uses here: MapReduce Patterns, Algorithms, and Use Cases.
  3. Hill Climbing. Introduces optimization over a non-exhaustible domain and leads to a whole array of powerful methods like gradient-descent, simulated annealing. Optimization allows us to do decision making, it's important.
  4. Binary search. Introduces logarithmic complexity and how the structure of data can change complexity characteristics of operations.
  5. Exponentiation (powers) by halving. Great example of a recursive attack. You would be surprised how many problems can be described as exponentiation (for an associative operation) of something: a number, a matrix and more. Again it's magical that associativity of an operation allows you to turn a linear factor into a logarithmic one.
  6. Floyd-Warshall. Graphs as matrices, shortest paths, negative cycles, dynamic programming in five lines of code.
  7. Inductive inference. Inductive inference. This idea on how to find programs that do certain things without having a human write them I believe is the key to the future of AI and simulating and understanding the human mind.
  8. Markov Chain Monte Carlo. Approximate integral, expected value computation based on a conditional specification of the probability distribution. This gives us a general way of doing data analysis.
  9. Shor's algorithm. Non-trvial example of a quantum algorithm that shows a significant complexity improvement. Reveals how quantum computing works.
  10. PageRank. How to iteratively solve for tightly related variables to extract metrics on graphs.

No comments:

Post a Comment