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

Ask HN: What's your favorite elegant/beautiful algorithm?

news.ycombinator.com

Post reply on HN
Print view View original

71–80 of 507 posts

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#71

Post by enedil »

josephg wrote: post #55
JonathanMerklin wrote: post #48

Earlier quoted context omitted.

Isn't this bit: const mid = Math.floor((right + left) / 2); susceptible to overflow? EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater than I expected.

Not in Javascript, where everything is a double precision float. You would lose precision at about 2^51, but that’s not a limit that will meaningfully affect us for good while.

Oh really? And what if you aren't storing the data? You just want to find such n, that f(n) >= m and f(n+1) < m. Now perhaps it might become an issue.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#73

Post by pimmen »

netgusto wrote: post #20

Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...

I've used it as a very simple equation solver in a pinch. Yes, it's a very naive approach for most equations, but getting started solving it satisfactory with a solution given is very welcome.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#74

Post by jeremysalwen »

The graph isomorphism protocol for Zero Knowledge Proofs. I think it's really elegant and easily understandable. Especially if you haven't seen a ZKP protocol before, it seems like it should be impossible, and then once you see the example, it seems so natural.

An example discussion from google: https://jeremykun.com/2016/07/05/zero-knowledge-proofs-a-pri...

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#76

Post by drjesusphd »

Gaussian integration.

You might have heard of "2nd order" or "4th order methods to calculate an integral. This means that the error drops off with the number of sampling points like N^-2 or N^-4, respectively. But Gaussian quadrature has spectral accuracy, which transcends this measure. Error goes down like an exponential of N.

Another neat feature is polynomials of degree 2N-1 or less are integrated exactly with this method. So if you have just 10 sampling points, you can calculate exactly the integral of a 19th order polynomial (times, perhaps, some known weighting function).

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#77

Post by OskarS »

KerrickStaley wrote: post #53

Union-find data structure: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Yeah, this is one of my absolute favorites as well. Such a neat idea. The analysis is also fun, where the complexity of operations is O(alpha(n)), where alpha(n) is the Inverse Ackermann Function. That function is just fun to contemplate.

You wanna flex your muscles with this data structure, this is a fun Project Euler problem: https://projecteuler.net/problem=186

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#78

Post by netgusto »

JonathanMerklin wrote: post #48
netgusto wrote: post #20

Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...

Isn't this bit: const mid = Math.floor((right + left) / 2); susceptible to overflow? EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater than I expected.

Thank you, fixed it!

const mid = Math.floor(left + (right - left) / 2);

https://stackoverflow.com/q/27167943

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#79

Post by Arqu »

By far my favorite is Depth First Search (DFS). It's almost a bread and butter algorithm for a lot of problems (at least for quick tests) with only a couple lines long in its recursive form. Some example usage: - combinations - permutations - generating sequences - exploring tree structures - finding paths - solving pretty much any search space problem and much more. It's not the most efficient for the large majority of these cases but it allows you to throw 10-15 lines of code to quickly test an idea before actually working on it.
Post reply on HN