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

391–400 of 507 posts

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

#391

Post by packetpirate »

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…

I thought I had an original and clever solution to TTT... my solution was to define all winning combinations as sets of (x,y) coordinate pairs and each time a player made a move, check to see if any of the winning combinations was a subset of the player's set of coordinate pairs.

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

#392

Post by manca »

Really nice list of algorithms here...

Math is definitely foundational for Computer Science and for that reason one of the most interesting algorithms I've personally encountered is the one for computing Principal Component Analysis (PCA)[1] using Singular Value Decomposition (SVD)[2].

It's just amazing how you can easily represent N dimensional objects in 2D. It's used a lot in Machine Learning. One of the interesting applications of the algorithm is Face recognition (eigenfaces method).

[1] https://medium.com/100-days-of-algorithms/day-92-pca-bdb6684...

[2] https://web.stanford.edu/class/cme335/lecture6.pdf

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

#393

Post by thijsvandien »

drexlspivey wrote: post #190
pawelgut wrote: 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.

And here is an elegant explanation of the Diffie-Hellman protocol https://www.youtube.com/watch?v=YEBfamv-_do

Another explanation that is not as technically accurate, but really clicked on me to understand how it's possible to establish private communication in the open, is the following:

You put your secret message in a box, put a lock on it that only you have the key to, and send it to the other party. They, unable to open it, put on a second lock of their own, and send it back. You remove your lock, leaving theirs, and once again send it to the other party. Finally, they remove their lock too and can open the box without anyone else having had that possibility.

What can also be inferred from this, is how DH is vulnerable to a man-in-the-middle attack. Someone involved in the delivery could pretend to you to be the other party and to them to be you.

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

#395

Post by packetpirate »

mindcrime wrote: post #324

There's something fundamentally appealing about Genetic Algorithms to me. Even though they don't apply everywhere, and even though "hill climbing with random restart" can be just as effective in many cases, there's just something awe inspiring about the idea of mimicking evolution. I also really like other related "nature inspired algorithms"[1] like Ant Colony Optimization, Particle Swarm Optimization, etc. [1]: htt…

Agreed. Ever since I first discovered them, I've decided that I eventually want to specialize in these types of algorithms. They may not be the most efficient algorithms to solve a problem, but they're incredibly fascinating, and their potential is endless.

I was actually considering implementing one during development of the game I'm working on to generate a soundtrack (since I'm not a musician), but the problem is the fitness function would require a user rating of each generated sound sample, and to get any kind of decent results, that would require me to personally listen to and rate thousands of songs. Either that or outsource it through SoundCloud or something.

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

#396

Post by HereBeBeasties »

api_or_ipa wrote: post #353
gyrgtyn wrote: post #342

Earlier quoted context omitted.

A cool thing about binary search is you can also use it in real life. It's great for troubleshooting.

`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?

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

#397

Post by aaaaaaaaaab »

munificent wrote: post #387
aaaaaaaaaab wrote: post #83

Earlier quoted context omitted.

>do it one pass in O(n) time Mind you, the “n” here is not the number of nodes! More precisely, Dijkstra’s algorithm runs in O(E + V * log V) time (if the priority queue is implemented with a heap), where E is the number of edges and V is the number of nodes. In the general case, E = O(V^2) (i.e. fully connected graph), so Dijkstra’s algorithm can calculate the shortest path to V nodes in O(V^2) time. It sounds less…

> And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! If there are negative edge-weights and cycles may occur, there is no shortest path between some nodes. You can keep going through a cycle whose total weight is negative getting "shorter" and "shorter". I…

Sure, but between "all edges have positive weights" and "there are cycles with negative total weight" there are still graphs that have negative edge weights, yet there's no negative-weight cycle.

Example:

V = { A, B, C }

E = { A -> B, B -> C, C -> A }

weight(A -> B) = 1

weight(B -> C) = 1

weight(C -> A) = -1

Post reply on HN