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

431–440 of 507 posts

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

#431

Post by _pastel »

muzzio wrote: post #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…

I have a pet implementation of the frequency map that I'm overly fond of, for ascii strings:

  (1) keep an array of length 127 that you re-use and set to 0 between calls
  (2) for each character in the first string, increment the array at the character's index
  (3) for each character in the second string, decrement the array at the character's index
If you end up with all 0s, it's an anagram.

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

#432

Post by chaoxu »

GautamGoel wrote: post #101
chaoxu wrote: post #17

Karger's randomized contraction algorithm for finding a min-cut. It's a common algorithm to introduce students into the world of randomized algorithms. Also a shameless plug. My friend and I came up with this pseudo-polynomial time algorithm for subset sum that can be taught in a single session. It is faster than the standard dynamic programming algorithm. https://arxiv.org/abs/1807.08248

I actually read some of this paper! I liked your FFT trick.

Thanks! Do you use that algorithm for anything in your research?

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

#433

Post by QML »

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 is also used in TCP with timeouts and ACKs. The idea is you have an expected timeout (ETO) and a retransmission time out (RTO). Initially, you set RTO to ETO and then you send a packet. If you don't get an ACK back, and the timer for the RTO expires, you then set RTO = 2 * RTO. Otherwise, reset RTO = ETO. I think they referred to this as 'exponential averaging' however.

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

#434

Post by sgillen »

sizzzzlerz wrote: post #321

The FFT algorithm is perhaps the most elegant and useful work of the 20th century. Modern communications would probably not be possible with out it but it's utility isn't limited to electronics It is used across the list of scientific disciplines and even in finance and economics. Next time you make a call on your smart phone, hoist a beer to Cooley, Tukey, and Carl Gauss

I have heard it called the most important algorithm of the 20th century. Not sure I buy that, I would say it's the most important algorithm in EE though.

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

#435

Post by mattkenefick »

Weighted randomization.

Objective: You have a list of things with a popularity score and want to get a random item from the list, but you don't want just ANY random item. You want it to be a generally popular item.

How it works: You take a key for the weight, we'll say `popularity` (0-100). And you have maybe 1,000 rows of content, each with said weight.

You sum up all the popularities to variable X. You set a random number between 0 and X; call it R. You iterate through your 1,000 rows (Y), and each iteration you subtract Y's `popularity` from your random number, R, and when R ---

Quick Example: https://jsfiddle.net/rL6a01ku/

Press "RUN" over and over to see the numbers change, but basically still stay the same.

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

#436

Post by sgillen »

tbabb wrote: post #404
rademacher wrote: post #370

Earlier quoted context omitted.

Wow. I'm surprised to see this on here. I used to work Johnson, he's is a super nice guy and always made time to have long conversations with me about optimization. I believe this algorithm is widely used in the video game industry?

Video games and anywhere you need a rigid body collision simulation. So TV & film visual effects is another common use.

Also researchers who need fast approximate physical dynamics. For example the Mujoco simulator or Drake.

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

#438

Post by [deleted] »

HereBeBeasties wrote: post #396
api_or_ipa wrote: post #353

Earlier quoted context omitted.

`git bisect` is an indispensible git trick. You give it commit where you know the bug exists, and one where you know it doesn't and it'll use binary search to help you find where the bug came from. It's absolutely wonderful.

I always struggle to see why people bang on about git bisect. You need tests to make it work. If you have tests, why aren't you running them continuously? If you're running them continuously, why do you need git bisect?

[deleted]

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

#439

Post by ncmncm »

nimonian wrote: post #339
toomuchtodo wrote: post #323

Earlier quoted context omitted.

It's also critical for factoring prime numbers and SETI signal intelligence processing. Truly a gem.

Factoring prime numbers?

Failing to factor them can be pretty important.
Post reply on HN