Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm impressed with the efficiency of some algorithms and I noticed the way the problem is solved can be and/or appear really unintuitive.

It may sound dumb, but I would like to know:

  • How do the authors come up with amazing algorithms? Do they just keep thinking about the problem and end up with the answer? Are they geniuses?

  • Which leads me to my next question: how long do they take to find the solution? Hours, days, months, years?

I know there isn't a definite answer to these questions. But I would like to know how it usually works regarding the most used/known algorithms.

share|improve this question

closed as too broad by Simon, MichaelT, gnat, tcrosley, Bart van Ingen Schenau Dec 5 '13 at 10:19

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

5  
Through the creative process, basically. There isn't any universal "algorithm for creating algorithms," because breakthroughs often require lateral thinking. –  Robert Harvey Dec 4 '13 at 16:55

4 Answers 4

up vote 11 down vote accepted

How are algorithms developed?

Generally, here's how algorithms are developed.

  1. Find a problem (or a problem with an existing solution)
  2. Find a solution to the problem
  3. Repeat steps 1 & 2 until you either can't find a problem or you can't fix it.

The resulting solution is the algorithm to resolve the problem.

"Really Useful" algorithms come about when you have an existing single-purpose algorithm and realize that it could be used in a different context with a few modifications. That realization is what re-triggers the iterative cycle.

This is where a lot of the generalization behind an algorithm comes from. And, as Robert Harvey stated, this extended iterative cycle is where software patterns come from.

It's equivalent to saying "I solved foo with this, and if I tweak that solution a bit then I could solve bar as well." And then that potentially extends into solving baz and so on as well. Solve enough challenges with the approach and it becomes generalizable as an algorithm or a pattern.

How long does that take?

It all depends upon the nature of the problem, the available solutions, and the tooling used to tackle the problem.


To help clarify Step #2 in the general approach: This is where a lot of the hard work and inspiration goes into creating an algorithm. Your first attempts at solving the problem will likely either fail or won't be all that elegant.

But you start with "well, how would I break that problem apart and solve it?" Remember that an algorithm is a step-by-step approach to solving a problem. So you break the problem down into steps and see how well that approach solves the problem. Also keep in mind that Problem Solving is a broad field of research. Some methods are more successful than others, and sometimes it's the unorthodox approach that develops the elegant solution.

share|improve this answer

Creating something new and better usually requires a flash of insight that can't really be taught or explained, but there are things you can do to help it along:

  • Understand the work of others. Start with college courses or textbooks on algorithms. Look for papers, blogs, Stack Exchange answers, or open source code for similar problems.
  • Determine the theoretical best asymptotic complexity. When you exceed that complexity, you'll know there is room for improvement.
  • Whiteboard it. Draw diagrams, lists, and issues. Think about how a human would solve the problem manually. Don't just jump into coding.
  • Experiment. Try different data structures. Try working in reverse from the obvious answer. Try preprocessing some data to make it quicker to work with. Try breaking the problem down into simpler steps. Try different techniques from existing algorithms.
  • Continuous refinement. 27-year world chess champion Emanuel Lasker said, "When you see a good move wait—look for a better one." Find the parts you don't like about your algorithm and make it better.
share|improve this answer
1  
Note that there are some problems for which the complexity is not yet known. Multiplication is one of those, for example. –  Jörg W Mittag Dec 4 '13 at 18:00

Algorithm development is a fundamental problem and as such, it is a popular topic in the research community.

Very specialized people with strong backgrounds in mathematic are working to solve new problems or improve old ones. Beside, good algorithm can be a significant advantage for some software compagnies, and you don't need a lot of money to experiment in this field.

So you have an army of bright people publishing papers hoping to become famous and using everything others are discovering, and easy to use almost free working environments to perform all the tests they need.

For each solution/improvement published, there will be a number of people asking themselves:

  • can I do better than this?
  • how can I use this to solve my other problems?

This process runs for years, and involves a lot of people (even if they are not directly interacting)

share|improve this answer

Many times you can adapt existing algorithms or piece together other algorithms.

Quick sort for example where someone realized they could subdivide a problem into smaller sets and utilize sorting methods that are more efficient with small sets. However, it just utilizes pre-existing algorithms for the sorting of elements.

Using quad trees to index geographical, pieces together pre-existing algorithms data structures, but applies them to a new problem.

So while some algorithms are truly innovative, alot of "innovation" is nothing more than someone realizing an existing tool fits a certain problem well. So if you want to develop algorithms, you should have familiarity with other existing algorithms.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.