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

271–280 of 507 posts

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

#271

Post by another-cuppa »

n4r9 wrote: post #244
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.

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.

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

#272

Post by another-cuppa »

skykooler wrote: post #221
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.

BogoSort is an algorithm. Not a very good algorithm, but an algorithm nevertheless.

No it absolutely is not.

The lack of fundamental computer science knowledge in this thread is alarming.

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

#273

Post by yboris »

A better voting algorithm for a better democracy: allow more than one vote per person. This eliminates numerous problems with today's one-vote-per-person. It's simple (no voter confusion) and results in better outcomes.

https://80000hours.org/podcast/episodes/aaron-hamlin-voting-...

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

#274

Post by jhallenworld »

yboris wrote: post #273

A better voting algorithm for a better democracy: allow more than one vote per person. This eliminates numerous problems with today's one-vote-per-person. It's simple (no voter confusion) and results in better outcomes. https://80000hours.org/podcast/episodes/aaron-hamlin-voting-...

No you should get just one vote, but dole out any number of fractions of it to whomever you wish as long as the total is 1.

If only the general population understood fractions :-)

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

#275

Post by kxyvr »

cultus wrote: post #240

The Galerkin method, which is the underlying concept that finite element analysis uses. Suppose you want to approximate the solution to a PDE with a finite sum of basis functions. The solution usually lives in an infinite dimensional Hilbert space, whereas our space of possible approximate solutions is a finite-dimensional subspace. To find the "best" solution that lives in the finite-dimensional basis-function (or t…

I like this, but I'll also contend that it's part of a broader question in applied math: What does it mean to be zero?

One way to define this is to say that a vector is zero when it's orthogonal to every other vector in some space. This gives rise to Galerkin and Petrov-Galerkin methods to solve differential equations. However, it also gives rise to linear system solvers such as conjugate gradient (CG).

Another way to define zero is to say that a vector is zero when it's norm is zero. This gives rise to least-squares finite element methods to solve differential equations. It also gives rise to linear system solvers such as GMRES.

Anyway, I agree with you, but wanted to add that it's an idea part of a greater strategy that gives rise to a huge number of good algorithms.

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

#276

Post by todd8 »

HN is great. There are so many fun algorithms listed here. My favorites are already mentioned but a few important ones are missing:

Boyer-Moore fast substring searching. Simple to understand and has great performance. [1]

Alpha-Beta game tree search. I really like Knuth’s paper on it. [2]

[1] https://en.m.wikipedia.org/wiki/Boyer–Moore_string-search_al...

[2] Artificial Intelligence Volume 6, Issue 4, Winter 1975, Pages 293-326

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

#277

Post by NicoJuicy »

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

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

#278

Post by tombert »

gregordv wrote: post #170

I always push my devs to really study the Bittorrent protocol. The elements of the protocol are all fairly easy to understand, but it's gorgeous to see how elegantly it solved a social problem rather than a computational problem. The tit-for-tat and fast-finish protocols are incredibly graceful ways to create virtuous cycles in a social/technical hybrid, and replaced very real vicious cycles in previous protocols. Va…

I second this; Kademlia has always struck me as one of the most beautiful and elegant algorithms out there; Bittorrent is wonderful too.

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

#279

Post by jules »

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 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.

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

#280

Post by laurentl »

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.
Post reply on HN