Ask HN: What is the big idea with algorithms?

I've had to look into the efficiency of my algorithms when doing batch processing on massive XML files - I managed to cut run-time by 80% by paying more attention to my algorithm's efficiency.

On the other hand, if I'm just sorting 5 entries alphabetically for some table, it's better to implement a quick-and-dirty algorithm that will take an extra 2 milliseconds to compute, than for me to spend half my day worrying about it's efficiency.

So generally speaking - people designing low-level systems are very worried about their algorithms, with good reason: If their code is slow or wasteful, their platform can't be used. If you're designing a web app, you'd probably waste more time than it's worth if you delve into that. It's just a question of priorities.

Could I whip up a tree balancing routine on a whiteboard on command? No! But, I'm aware that such algorithms exist and what situation I'd need to apply them to.

I think this is what you should shoot for. As for Algorithms in a Nutshell, if it is the book I'm thinking of then bravo. I like how the authors chose to present the algorithms using code and not the awful psuedo-code found in most algorithms texts.

seriously, though, this is a pretty broad, abstract concept. an algorithm is, more or less, a set of instructions to solve a problem. they didn't have some sort of magical genesis, and everyone uses them on a daily basis.

Are there any math whiz kids on HN? (other than cperciva)

There are many smart people on HN, but I don't think there are math whiz kids. This is a hacker forum, not a math forum like AoPS. Sometimes we discuss stuff like complexity and algorithms, but most of the time, we rant on Ruby x Python or why kids these days want to build social networks for dogs instead of sending astronauts to Mars, or why big corporations are evil and small startups rock, or why PG is a supreme master and every single essay of his is nothing less than the truth. We are such cool kids we even have our own hacker-ghetto slang... including hideous terms like "ramen-profitable" ;-)

I know a forum where there's even a Fields medalist, and that is on quantitative finance. Whoever says that HN is made of math whiz kids probably knows very little math.

For instance chess is relatively easy to program where as go is quite a bit more difficult. ---------------------------------------

Here's a very good quote from wikipedia that might make it clearer:

The thesis is widely considered to be a good rule of thumb for real-life problems. Typical input lengths that users and programmers are interested in are between 100 and 1,000,000, approximately. Consider an input length of n=100 and a polynomial algorithm whose running time is n^2. This is a typical running time for a polynomial algorithm. (See the "Objections" section for a discussion of atypical running times.) The number of steps that it will require, for n=100, is 100^2=10000. A typical CPU will be able to do approximately 109 operations per second (this is extremely simplified). So this algorithm will finish on the order of (10000 ÷109) = .00001 seconds. A running time of .00001 seconds is reasonable, and that's why this is called a practical algorithm. The same algorithm with an input length of 1,000,000 will take on the order of 17 minutes, which is also a reasonable time for most (non-real-time) applications.

Meanwhile, an algorithm that runs in exponential time might have a running time of 2^n. The number of operations that it will require, for n=100, is 2^100. It will take (2^100 ÷ 109) ≈ 1.3×1021 seconds, which is (1.3×1021 ÷ 31556926) ≈ 4.1×1013 years. The largest problem this algorithm could solve in a day would have n=46, which seems very small.

http://en.wikipedia.org/wiki/Cobham%27s_thesis

AIT and computational complexity theory arguably underlay all other sciences. They allow us to define randomness (http://www.cs.auckland.ac.nz/~chaitin/georgia.html), pattern, probability (http://www.scholarpedia.org/article/Algorithmic_probability), inference (http://www.wisegeek.com/what-is-solomonoff-induction.htm), ignorance, and perhaps one day consciousness.

They allow us to prove, with absolute certainty, whether we are talking to a deity ( http://scottaaronson.com/blog/?p=56), and to prove that some questions will forever be beyond our grasp.

Even discounting Zuse and Wheeler's "It's from Bits" conception of information and computation as the basis of physics (http://en.wikipedia.org/wiki/Digital_physics), these disciplines promise to help us solve our hardest and most interesting problems by, first of all, telling us whether they are solvable at all, and if so, whether they are solvable before the heat death of the universe. Consider that Goedel, Cohen, and Turing struck down the Continuum Hypothesis from Hilbert's list of open problems, allowing us to abandon a futile line of inquiry and focus on other problems. Current developments in quantum computability theory may similarly strike down vast swathes of sterile ideas, directing us toward questions whose answers are solvable.

Input X, Output 0

Algorithm:

while x is not equal to 0, subtract 1 from x

When x equals 0, return x.

This is a finite series of step to go from input (x) to output (0). I just subtract 1 from x over and over until I have 0.

No matter how complex algorithms can get they are basically the same thing, at least in sequential programming - I don't know too much about other more recent stuff to be honest - but traditional programming is just taking an input, applying a set of operations on the input, one at a time, until the set of operations is completed and you have an output. An algorithm is just a "recipe" or a set of operations. A recipe is a series of steps to be done to food to make a meal. Similarly an algorithm is a series of steps to be done to an input to make an output. Most languages are basically like this in programming: FORTRAN, C, ASSEMBLY are all basically this same idea of sequential, finite operations on inputs.

I now think in terms of rules, context and complexity. I mostly think about distributed algorithms and the key to me is always a small set of rules that all nodes must follow. Rules are generally reactions to events, involving communication and/or state changes. Much of the time the rules follow from some constraint, such as complexity requirements or limited information. There are often different possibilities so you consider the trade-offs based on your context. I approach computational problems in the same way. I figure out data elements need to interact and then come up with some reactive rules. The computation is the chain-reaction of those rules.

The algorithm follows from the rules. Essentially it is a formalization of the ideas into an iterative instruction framework. The algorithm can then be implemented on a computer by any competent engineer and may be analyzed mathematically (e.g. for formal proofs).

So for example, physics describes the answer to "where will this spacecraft be five years from now?" while to compute a numerical answer you need to apply some particular algorithm (like a differential-equation solver).

Most of the algorithms in "Nutshell" are what you might call core-level methods of figuring things out. For example, the book describes different sorting algorithms. From your question, you sound more interested in what kinds of problems demand sorting (for example). For that, you might try a bigger-picture book, for example Steven Skiena's "Algorithm Design Manual." It goes into less detail about actual implementation, and more detail about what the algorithms do for you, and when you might apply them.

As Dijkstra said "Computer Science is no more about computers than astronomy is about telescopes."