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

191–200 of 507 posts

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

#191

Post by yellowflash »

otikik wrote: post #171

I like the A* pathfinding algorithm. It's not particularly elegant or beautiful on itself, and it's very dependant on the heuristics applied & the topology of the terrain used. Yet the results tend to be quite pleasing to watch. Also, it has a great website dedicated to it, with lots of interactive demos: http://theory.stanford.edu/~amitp/GameProgramming/

Actually it's pretty elegant by itself, Consider this all traversals are same,

val someDS;

while(!someDS.isEmpty()){

  addChildren(someDS.pop())
}

Now replace, someDs with

Queue -> BFS

Stack -> DFS

Priority Queue, with priority of distance so far -> Dijkstra.

Priority Queue, with distance + heuristic -> A*

Its beautiful.

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

#192

Post by lifthrasiir »

akhilcacharya wrote: post #185
pimmen wrote: post #73

Earlier quoted context omitted.

I've used it as a very simple equation solver in a pinch. Yes, it's a very naive approach for most equations, but getting started solving it satisfactory with a solution given is very welcome.

...wait, how? I’ve never heard of a use like this.

If f is monotonic and continuous, you can solve f(x) = y for x by successively narrowing an interval [a, b] where f(a) <= y <= f(b) (or vice versa for decreasing functions). In the case that the range of f spans the entire real numbers, the initial range can be determined as the smallest range [-2^k, 2^k] where k is an integer (a strategy often used for open-ended binary search).

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

#195

Post by moftz »

otikik wrote: post #171

I like the A* pathfinding algorithm. It's not particularly elegant or beautiful on itself, and it's very dependant on the heuristics applied & the topology of the terrain used. Yet the results tend to be quite pleasing to watch. Also, it has a great website dedicated to it, with lots of interactive demos: http://theory.stanford.edu/~amitp/GameProgramming/

The development of "Shakey the robot" led to the discovery of A* along with a few other algorithms.

https://en.wikipedia.org/wiki/Shakey_the_robot

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

#197

Post by another-cuppa »

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

Earlier quoted context omitted.

K-means is not an algorithm, it's a heuristic for an Np-hard problem.

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.

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

#198

Post by another-cuppa »

wnkrshm wrote: post #146
another-cuppa wrote: post #137

Earlier quoted context omitted.

K-means is not an algorithm, it's a heuristic for an Np-hard problem.

Isn't a method that gives an approximate or best-fit estimate to a problem still an algorithm, if it terminates?

No. You can't prove that k-means does anything useful.

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

#200

Post by kmike84 »

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