Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Most Important Algorithms

risc.jku.at

Post reply on HN
Print view View original

41–50 of 50 posts

Re: The Most Important Algorithms

#41

Post by nostrademons »

igravious wrote: post #39
nostrademons wrote: post #31

Earlier quoted context omitted.

ii.) I'd noticed a while ago that all graph traversal algorithms follow the same pattern. There is a white set of undiscovered nodes, a grey set of discovered-but-unvisited nodes, and a black set of visited nodes. To execute the graph traversal, you push a start node into the grey set, and then recursively pop a node off the grey set, add any children of it that are currently in the white set to the grey set, and rep…

Hi nostrademons, do you mind if I put this observation onto Wikipedia if it is not already there? I would add the cyclic/acyclic observation of sb's reply also. http://en.wikipedia.org/wiki/Graph_traversal is just a stub, it could nearly go there.

I don't mind, but I'm guessing it'll get tagged with [citation needed], and I don't know what an appropriate citation for it is.

Re: The Most Important Algorithms

#42

Post by jefffoster »

dododo wrote: post #4

quite a lot of structure amongst these algorithms that the list misses out: - dynamic programming comes from solving Bellman's equation and Q-learning is an approximate means of doing dynamic programming. - It's possible to do beam a* search, where beam search, a* search, and best-first (greedy) search are special cases. - in the continuous domain, greedy search is essentially gradient ascent. - you can use discrete…

The search chapter in PAIP has an excellent description of A* search, beam search and best first search that shows the relationship between the algorithms. The code is available on-line (http://norvig.com/paip/search.lisp).

Re: The Most Important Algorithms

#43

Post by arethuza »

nostrademons wrote: post #14

This reads like a textbook, i.e. it's algorithms that are highly useful to CS professors and students but not necessarily to practitioners. If I had to pick a top-10 list based on my professional experience, it would be: 1. Tree traversal. This comes up all the time , from directory walks to DOM traversal to code analysis to folds over abstract data types. It's also something that you need to know and can't always re…

I'd add some crypto algorithms to that list: cryto hashing (as someone noted below, not every hash is a crypto hash), symmetric and asymmetric encryption, digital signing.

Diffie-Hellman key exchange as well as it is so simple and so wonderfully counter-intuitive.

Re: The Most Important Algorithms

#44

Post by miguelpais »

A* is not just that. The way it is said seems to imply that it is equal to Best First Search. Best First Search only relies on the heuristic function, so for the following graph, where A is the start node and h is the heuristic function:

+---A---+

|...........|

B h:1....E h:4

|

C h:2

|

D h:3

The traversal order according to Best First Search would be:

{A, B, C, D, E}

While A* will search by g(x) = h(x) plus d(x), the latter being the distance function from the start note to the given node. So, assuming the distance function to be equal to the depth of the node in the tree it would traverse it this way:

{A, B, C, E, D}

g(D) = h(D) + d(D) = 3 + 3 while g(E) = h(E) + d(E) = 4 + 1 = 5, so E goes first.

Re: The Most Important Algorithms

#45

Post by gadtfly »

nostrademons wrote: post #41
igravious wrote: post #39

Earlier quoted context omitted.

Hi nostrademons, do you mind if I put this observation onto Wikipedia if it is not already there? I would add the cyclic/acyclic observation of sb's reply also. http://en.wikipedia.org/wiki/Graph_traversal is just a stub, it could nearly go there.

I don't mind, but I'm guessing it'll get tagged with [citation needed], and I don't know what an appropriate citation for it is.

The extent of my experience on the topic is in half-comprehending hobbyist's awe and the inclusion of okmij on my "personal heroes and demigods" list. The only word I could half-heartedly associate with this structure is the incredibly lame "hylomorphism"... which actually kinda generally expresses the pattern of much of computing. It's 5 AM and I'm going to sleep, but I'll leave you with the the most plausible leaves of a very brief search towards finding some recognized formal name for this structure:

http://blog.sigfpe.com/2009/07/monad-for-combinatorial-searc... http://spivey.oriel.ox.ac.uk/mike/search-jfp.pdf http://www.cs.au.dk/~gerth/papers/jfp96.pdf

If you really don't like yourself, try digging here:

http://hackage.haskell.org/packages/archive/pointless-haskel... http://comonad.com/reader/2009/recursion-schemes/

Re: The Most Important Algorithms

#46

Post by beagle3 »

_delirium wrote: post #37
beagle3 wrote: post #19

Earlier quoted context omitted.

I don't agree with that list, but I think quicksort is given way more weight than it deserves. I guess it's a desired result of whomever named it "quicksort". It's not particularly quick, has horrible worst case guarantees (which, if you care to improve, would make it slower still and very complicated), and is easy to get wrong on many accounts (repeating elements; already sorted input; unlimited recursion depth). he…

The main advantage to quicksort is that it's still the fastest average-case-in-practice of the common algorithms. If you want an O(nlogn) worst-case, introsort combines quicksort, which is fast on average but O(n^2) worst-case, with a fall-back to an O(nlogn) heapsort, with a guarantee that it'll never take more than O(nlogn) before it falls back, making it still worst-case no worse than O(nlogn) . It'll of course be…

> The main advantage to quicksort is that it's still the fastest average-case-in-practice of the common algorithms.

I don't think that's true if you average over the available distribution of _implementations_ in the wide. Almost all implementations do one to three of the "crimes" I mentioned above. And frankly, I've met too much real world cases that triggered an n^2 behaviour on an existing implementation to ever settle for anything with worse than n*log n worst case.

If you're looking for the fastest-in-both-theory-and-practice algorithm, that's TimSort, but it's not in place. The places _in practice_ where Quicksort is the right answer are few and far between. I haven't seen any in the last 10 years.

Re: The Most Important Algorithms

#47

Post by Retric »

nostrademons wrote: post #31
sb wrote: post #28

Earlier quoted context omitted.

Nicely observed, but I have two just for the records (again, I know): i.) this is a list of/for CS professors; RISC expands to Research Institute for Symbolic Computation which is a CS/Math department of Prof. Buchberger who discovered the famous Groebner bases. ii.) AFAIR (too many years gone since), the A* algorithm is pretty much a generalization for graph traversal. I remember my professor showing us that how by…

ii.) I'd noticed a while ago that all graph traversal algorithms follow the same pattern. There is a white set of undiscovered nodes, a grey set of discovered-but-unvisited nodes, and a black set of visited nodes. To execute the graph traversal, you push a start node into the grey set, and then recursively pop a node off the grey set, add any children of it that are currently in the white set to the grey set, and rep…

It's a nice theory but there is a second class which basically consists of two shades of White, Grey, Black, and Red.

Let's say you’re building a system to quickly find the degree of separation between two people on a network. For simplicity assume each node connects to 4 random other nodes. If you start from one end and do a breadth first search you would need to try ~(4^N) nodes to find the link. However, if you start from both ends and do a breadth first search you can try ~2 * (4^(N/2)) nodes to find that same connection.

Re: The Most Important Algorithms

#48

Post by mahmud »

sb wrote: post #30
iamanet wrote: post #5

Earlier quoted context omitted.

I am going through Cormen et al. with the objective of getting my feet wet but the whole process is painfully slow. I thought it would be nice to have at least some familiarity on the widely used algorithms across the globe. However, you are right on ditching programming languages with huge boot times. I am happily trying out my algorithms in Python.

CLR is an extremely well written algorithms textbook, but I use it more as a reference than for self-study. My first algorithms book was Sedgewick's Algorithms (where all algorithms were presented in Pascal), which is a very good algorithms text that is much lighter on several aspects. Recently, however, I came across the following gem: Algorihtms + Data Structures = Programs, by Niklaus Wirth. (an Oberon version of…

A fellow Oberon fan! Wirth has a rare talent for language design, and I cut my compiler hacking teeth on Oberon, thanks to his tiny booklet on the language and its implementation.

Re: The Most Important Algorithms

#49

Post by sb »

mahmud wrote: post #48
sb wrote: post #30

Earlier quoted context omitted.

CLR is an extremely well written algorithms textbook, but I use it more as a reference than for self-study. My first algorithms book was Sedgewick's Algorithms (where all algorithms were presented in Pascal), which is a very good algorithms text that is much lighter on several aspects. Recently, however, I came across the following gem: Algorihtms + Data Structures = Programs, by Niklaus Wirth. (an Oberon version of…

A fellow Oberon fan! Wirth has a rare talent for language design, and I cut my compiler hacking teeth on Oberon, thanks to his tiny booklet on the language and its implementation.

I think his talent for language design is undisputed. But his talent for writing easily equals his talent in programming, e.g., I never came across any work of Wirth that was not well written and contained interesting insights. A couple of years back, I came across the very interesting paper "Good Ideas, Through the Looking Glass" (2005) http://www.cs.inf.ethz.ch/~wirth/Articles/GoodIdeas_origFig.... which is probably not as Wirth-esque as his books, but still an interesting review of what happend in our discipline, looking back.
Post reply on HN