Live data from Hacker News

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

news.ycombinator.com

301–310 of 507 posts

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

#301
post #8

Diffie–Hellman. I know that cryptography can get much fancier and more clever, but Diffie–Hellman took a concept my intuition told me was impossible and showed that it's possible in a really simple, elegant way. Learning about it was the first time I realized how beautiful the math behind computer science is. It's also a great insight into just how fundamental the concept of computational complexity is.

Second to this.

Totally blew my mind back then when I was trying to understand how asymmetrical cryptography works.

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

#303
Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other:

The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1]

So to determine that two words are anagrams of each other, you can assign each letter to a unique prime number (a = 2, b = 3, c = 5 etc.), then compute the product of those numbers, and if they're equal then those two words are anagrams.

[1] - https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...

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

#305

I'm surprised no one mentioned PageRank (or maybe I missed it). Another favorite is RAFT, simply because of how elegant and simple it is and how easy it is to understand. Also - I used to work in a company that did P2P video streaming (pre WebRTC) and the way the protocol leveraged Reed Solomon Coding was just awesome. https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...

Seconding this. Its super easy to understand and explain to others (albeit implementation I have found to be somewhat more challenging when you dig into the details)

Yeah, once you start considering log rewrites I remember it got a bit more challenging. But the main idea is super elegant and beautiful.

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

#306

The "2 watched literal" algorithm used in sat solvers (here is a random blog post I found by googling http://haz-tech.blogspot.com/2010/08/whos-watching-watch-lit... ). The algorithm has many lovely features. It is very efficient -- it is used in basically every SAT solver with minimal modifications. It's not entirely trivial it works, particularly the backtracking part. It is a good example of how there are algorith…

this is a neat way to avoid moving those pointers around: https://www.cs.kent.ac.uk/pubs/2010/2970/content.pdf

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

#307
post #279

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 like this version: low = -1 high = arr.length while(high - low > 1){ mid = (high + low)/2 if(arr[mid] This eliminates all branches from the body of the loop (gets compiled to conditional move). It's also more general because it can be used to find the right position to insert a new element in a sorted array.

and it's also a broken version.

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

#308
My favorite elegant and trivial algorithm has always been merge sort as it looks in Lisp/Scheme. My favorite messy algorithm is simulated annealing for its intuitive sledge-hammer approach. In graphics I like some off-screen rendering methods which are elegantly simple in applying brute-force to use the whole frame buffer as a lookup table.

For object picking (determining what the user clicked on) in a complex visualization, it is often easiest to draw all objects with a simple color-mapping renderer which follows the same occlusion rules as your visualization but renders each object as a solid blob in a distinct color. You draw the scene, look at the pixel color under the mouse, and use the color as an index into the table of objects.

For ray-cast volume rendering, you have a problem somewhat like object picking but you have to solve it simultaneously for all pixels in the rendered scene. You have to determine the ray intersections of each pixel's perspective through your volumetric data grid, so you can run a sampling loop to integrate the 3D scalar field values along that ray. When your grid has a simple cube/box shape, you can render a polygonized box with the viewing perspective and trivially color-map it so each surface of the box has an RGB value encoding its XYZ volume coordinates. Your volumetric pixel shader, running on the GPU, can then independently lookup these XYZ positions out of screen-sized buffers to determine the start and end positions for each screen pixel's ray integration loops as 3D texture coordinates.

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

#309

Shamir's Secret Sharing. I don't have a smart description, it's just wonderful. Split the secret in N parts, require N - K parts to reconstruct it. Use cases are numerous.

SSS is one of my favorites because it takes concepts I learned from basic algebra, transliterates then to finite fields, and turns them directly into industrial-grade crypto.
Post reply on HN