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

291–300 of 507 posts

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

#291

Post by mark-r »

kmike84 wrote: post #200
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...

Regarding "very simple" - as I recall from some book, first bug-free implementation appeared only after several years after invention / initial description of the algorithm. From wikipedia: "A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks" ( https://en.wikipedia.org/wiki/Binary_search_algorithm ).

Someone did a blog about that book, and challenged people to do their own bug-free implementations. https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-1...

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

#292

Post by ritwikgupta »

NicoJuicy wrote: post #277
gwbas1c wrote: post #225

Exponential backoff: I don't know if this is a published algorithm. Basically, background processes need to keep retrying an operation until it succeeds. (Make an API call to a server, upload a file, ect, ect.) If the retry interval is too small, you can DOS the remote server. (Server returns a 5xx error because there's a corner case that hits a defect.) But, if the retry interval is too large, your background proces…

This can't be an algorithm? I implemented it on a loop and a limit duration ( an hour) and a Max interval of a minute ( starting from 5 seconds) in 5 lines of code

A short algorithm doesn't make it any less of an algorithm :)

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

#293

Post by n4r9 »

another-cuppa wrote: post #271
n4r9 wrote: post #244

Earlier quoted context omitted.

As far as I can tell you're only arguing against poor implementations of K-means. If you demand that the score strictly improves at each iteration then the algorithm must terminate.

And how do you "demand that the score strictly improves"? It's an NP-hard problem.

K-means implementations generally terminate once there's an iteration where the score doesn't improve. This happens when there is convergence to a local minimum or - less likely - the state hops between two nearby local minima with the same score. But it will terminate on something, and most of the time that something will be pretty good.

I saw your mention of Knuth elsewhere, I looked it up and he demanded that

> An algorithm must always terminate after a finite number of steps ... a very finite number, a reasonable number

This is a pretty niche characterization and almost certainly not what the original post was asking for. However, I concur that there is no guarantee on how quickly K-means terminates or on how good the output will be,. But... if you're going to be that strict about it you would even have to rule out the Simplex Algorithm, which everyone I've ever spoken to thinks of as an algorithm.

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

#295

Post by another-cuppa »

billfruit wrote: post #214
another-cuppa wrote: post #197

Earlier quoted context omitted.

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.

In that sense kmeans may be better referred to as a 'computational method' rather than an algorithm.

Indeed.

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

#297

Post by Const-me »

narag wrote: post #38

B Trees. You can call them a set of algorithms or a data structure if you prefer, but its core idea can be expressed as an algorithm: making the root of the tree emerge from leaves. It's kind of democratic ! Edit: it's also a massively practic idea that powers most databases.

And many filesystems, too, NTFS, Ext4, etc.

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

#299

Post by zinclozenge »

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…

Kleinberg and Tardos start off their algorithms book with this problem, except they formulate it in terms of college juniors seeking internships and employers.

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

#300

Post by chrisshroba »

laurentl wrote: post #280
rodovich wrote: post #227

My first programming project was a tic-tac-toe game with a computer opponent. I painstakingly copy-pasted about a hundred nested `if` statements to check for a winner & decide the computer’s next move. Several years later I saw a Matlab demo that did this by indexing the grid using values from a 3x3 magic square[1]. In a magic square, every row, column, and diagonal has the same sum. So checking for a winner was just…

Nitpick: this only works if the player played exactly three moves (in the version of Tic Tac Toe I know you can play for up to 5 moves). Generalizing to 4 moves is fairly simple, to 5 moves less so; you can test all '3 from 5' combinations, which is only 10 possibilities, but I doubt the code to do this is easy to read and understand after the fact.

I'd disagree here; I still think it's quite elegant. For example, in python, it would look something like

  from itertools import combinations
  magic_square = [2,7,6,
                  9,5,1,
                  4,3,8]
  def did_user_win(moves):
    # Convert moves to magic square values
    magic_values = [magic_square[move] for move in moves]
    # Check if any sum of three moves equals 15
    for three_values in combinations(magic_values,3):
      if sum(three_values) == 15: return True
    return False
Post reply on HN