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

201–210 of 507 posts

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

#201

Post by tomp »

mattyw wrote: post #158
tomp wrote: post #144

Earlier quoted context omitted.

I love this algorithm (I like implementing type systems) but I always feel a bit naughty when I implement it, as AFAIK it can't be implemented with immutable data structures (not efficiently, at least).

I like implementing type systems Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.

Check out https://github.com/tomprimozic/type-systems there's been a few HN threads about it as well. I can also answer any specific questions you have, or if you want further resources I can try and find them... (there's a good online book I have in mind, but I've no idea how to find it right now!)

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

#202

Post by Juminuvi »

calciphus wrote: post #56

The Gale-Shapley Algorithm to solve the "Stable Marriage" problem. 2012 Nobel Prize in Economic Sciences for its wide-ranging use in medicine, education, and resource allocation. It's fairly easy to implement a basic version of it, feels intuitively obvious once explained, and has been applied to everything from organ transplants to student placement in elementary schools. Really, any place you have two groups where…

Interesting! I knew that med school applicants were accepted on some sort of ranking and matching process but didn't realize there was a real algorithm behind it. This, or one similar, seems to be what's behind it.

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

#203

Post by abhgh »

superice wrote: post #175

I have always liked DBSCAN: https://en.wikipedia.org/wiki/DBSCAN DBSCAN is used for clustering in applications, much like k-means clustering, but in k-means clustering, the number of clusters must be known in advance (hence the k) DBSCAN solves this problem by for every point in the graph checking if a certain threshold of vertices is within a certain radius. If this is the case, it will add these vertices to the new…

If you like DBSCAN, I would recommend checking out OPTICS. It is not a clustering algorithm per se, but generates information from which clusterings for multiple settings of DBSCAN parameters can be "queried" cheaply. The DBSCAN and OPTICS papers share an author. One my favorite algorithms. This is the original paper - [1], and this looks like a helpful presentation on the topic - [2]. Since you mention k-means, I would point out that unlike k-means which finds convex-shaped clusters only, DBSCAN/OPTICS identify clusters of any shape.

[1] http://www.dbs.ifi.lmu.de/Publikationen/Papers/OPTICS.pdf

[2] https://www.cse.buffalo.edu/faculty/azhang/cse601/density-ba...

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

#204

Post by alanbernstein »

andrath wrote: post #168

Duff's device. Because you will first look at it in disgust, but then you realize how clever it really is. See: https://en.wikipedia.org/wiki/Duff%27s_device

It's interesting how this seems to be not quite an algorithm - I suppose "device" is an appropriate name. The "See also" section on Wikipedia leads to some good stuff.

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

#205

Post by jbottoms »

Dijkstra's Shunting algorithm, also called the Twin Stack algorithm, is a work of art in its simplicity and function. It can convert an algebraic express to a RPN sequence that can be executed on a stack machine. I like to use it to teach students the value of using stacks.

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

#206

Post by bsenftner »

andrath wrote: post #168

Duff's device. Because you will first look at it in disgust, but then you realize how clever it really is. See: https://en.wikipedia.org/wiki/Duff%27s_device

Quite a few EA Sports games have Duff's Device in locations of computational bottlenecks. I know because I put them there. Wonderful little mechanism.

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

#207

Post by zaphar »

another-cuppa wrote: post #197
n4r9 wrote: post #149

Earlier quoted context omitted.

It is absolutely an algorithm in the sense of "a set of rules to be followed". I think you mean that it doesn't guarantee an optimal solution. That just means it's a heuristic algorithm, same as simulated annealing is a heuristic algorithm for solving optimisation problems.

Nope. An algorithm has to be effective. You can find pathological cases for k-means such that it will never converge on anything useful. So if you set your termination case to be convergence it will never terminate and if you don't then it will never be effective.

I think you might be in the minority in this opinion. Many algorithms have pathological cases but are still considered algorithms

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

#210

Post by gattr »

I'm into computer graphics, so for me it's raytracing. The principle is simple, so one can quickly code some "shiny spheres" example, but then there's a lot of interesting connected stuff to learn: linear algebra, spatial data structures, Monte Carlo extensions, ...
Post reply on HN