Ask HN: What is your favourite algorithm?

https://news.ycombinator.com/item?id=6340636

by redxblood • 13 years ago

16 15 13 years ago

news.ycombinator.com

cpncrunch2• 13 years ago

My favourite would have to be one that I invented myself. I guess like a lot of people here I occasionally end up having to figure out algorithms to solve particular problems. That is one of the most rewarding aspects of being a programmer.

cpncrunch2• 13 years ago

Not sure why cheery was downvoted - it was a legitimate question. Seems like he/she's been hellbanned for no apparent reason.

Anyway, to answer your question I haven't invented anything particularly groundbreaking, just still I need to do my job. Things like 3d collision detection, line-of-sight detection, etc.

As a more concrete example, in the days before broadband I had a problem with transmitting the positions of multiple players in a multi-user game environment. Say you have hundreds of users on dial-up, some with 10ms ping time and others with 100ms. The 10ms users will be able to transmit their position 100 times a second, but the 100ms users can only transmit 10 times a second (assuming they wait for a reply). It doesn't make sense to transmit 100 movement updates to the slow clients, as you'll just overload their connection with unnecessary data. So what is the best solution? The algorithm I came up with is this:

- server maintains "last position" coords plus timestamp for each client - whenever server receives a position update from a client x, it sends the positions of any clients who have sent updates since client x last sent an update

Not groundbreaking, but it took quite a lot of thought to come up with it. The beauty is that it only transmits the data that is needed - the fast clients get fast updates (but without sending any duplicated data), and the slow clients get slow updates. It's simple, elegant and efficient, which is the best type of algorithm.

PS, I don't work in the games industry or with 3d graphics - all that stuff was really just my hobby. I'm pretty sure I've had to come up with some algorithms for the stuff that pays the rent (which is also pretty interesting), although I can't think of any off the top of my head. I did come up with a sound compression algorithm using FFTs, but abandoned it for an off-the-shelf one that worked much better. For the most part it is better to use algorithms that someone else has already figured out and turned into code rather than reinventing the wheel.

blubbi2• 13 years ago

Dijkstra's algorithm ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm )

It is a really elegant algorithm and addresses a real-world problem. A teacher of mine once showed us the basic idea behind it:

He connected various bits of wood (=nodes) using strings (=edges). Then he picked up one bit of wood (=starting node) and slowly moved it upwards. Every time when a new node moves, it is an indication that the shortest path between the start node and the new node has been found. He did this until he reached the desired end node. The shortest path between the two nodes is in the end clearly visible, because the path between two nodes A and B that are part of the path between the start and end node is always the shortest path possible.

It is really simple if you think of it as a physical model, unfortunately I could not find a picture of it online :(

jogzden• 13 years ago

The gif on wikipedia (http://i.imgur.com/ZQMaGhj.gif) was actually a very good example. Thanks! :D

tbirdz• 13 years ago

It's more of a method than an algorithm, but I'm a big fan of Dynamic Programming.

alok-g• 13 years ago

Chart parser, http://en.wikipedia.org/wiki/Chart_parser

sharemywin• 13 years ago

Restricted Boltzmann Machine

Rickasaurus• 13 years ago

Gale–Shapley algorithm (for the stable marriages problem) http://en.wikipedia.org/wiki/Stable_marriage_problem

It's a beautifully simple algorithm with uses in almost every field.

Here's a more informative link http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-a...

WasimBhai• 13 years ago

Viterbi. Beauty.

junto• 13 years ago

I like the Monte Carlo algorithm: http://en.wikipedia.org/wiki/Monte_Carlo_algorithm

LarryMade2• 13 years ago

LSL LSR PHA PLA BYT BYT BYT

Shift to the left, Shift to the right, Push-a, Pull-a Byte, Byte, Byte!

Sorry, I just couldn't resist...

mistabrando• 13 years ago

Sleepsort of course

#!/bin/bash

function f() {

    sleep "$1"
    echo "$1"

}

while [ -n "$1" ]

    f "$1" &
    shift

done

wait

lsiebert• 13 years ago

I don't know that I have favorites. That said, Radix sort is kinda cool. It's O(n * k), where k is the number of digits in the number, but it's possible to have k be a constant if there is a limit (like an int can only be so big) meaning you can have an O(n) sort.

helpermethod• 13 years ago

Insertion sort. Easy to implement (easier than BubbleSort), very fast for small data sets. Can be used in merge sorts / quick sorts when the set size becomes small.

andrewhillman• 13 years ago

I really dig AI algorithms like...

http://www.norvig.com/spell-correct.html

Simplicity is beautiful.

Ask HN: What is your favourite algorithm?

Related Stories