from Hacker News

Ask HN: What are your favorite algorithms?

by EFruit on 1/29/17, 11:53 PM with 89 comments

Post any algorithms you think are cool, inventive, or useful. PDF links or blog posts are appreciated.

My current favorite is SWIM. https://www.cs.cornell.edu/~asdas/research/dsn02-swim.pdf

  • by theemathas on 1/30/17, 5:50 AM

    The Fastest and Shortest Algorithm for All Well-Defined Problems: https://arxiv.org/abs/cs/0206022

    Abstract: An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof. M has broader applicability and can be faster than Levin's universal search, the fastest method for inverting functions save for a large multiplicative constant. An extension of Kolmogorov complexity and two novel natural measures of function complexity are used to show that the most efficient program computing some function f is also among the shortest programs provably computing f.

    The catch is that the constants in the big-O are enormous.

  • by DDR0 on 1/30/17, 7:10 AM

    Given the head of a linked list, how do you determine if it loops? eg, an l-shaped list is easy to determine - you simply process each element in the list until you find one without a subsequent element. But what if it's a 9-shaped linked list? You'll never run out of elements, so the best you could seem to do would be to store a reference to each element and check against all references to see if you've found a duplicate.

    There's a way to do it in O(1) space, though.

    If you start off two runners in the list, and each "step" move one twice and the other only once, if there's a loop they will eventually run into each other and be processing the same element. Simple, elegant, and nothing I'd have ever thought of. :)

  • by wmu on 1/30/17, 8:11 AM

    1. Lempel-Ziv compression algorithms (both LZ77 and LZ78). They are practical, even if one code their basic versions will get good compression ratio. Moreover, they opened the whole big chapter of data compression (LZW, LZSS and more). 2. The algorithm behind rsync. Nice one. 3. Jarvis algorithm for finding convex hull. 4. Speaking of data structures I like xor-linked list, it's neat.

    [1] https://en.wikipedia.org/wiki/LZ77_and_LZ78 [2] https://en.wikipedia.org/wiki/Rsync#Algorithm [3] https://en.wikipedia.org/wiki/Gift_wrapping_algorithm [4] https://en.wikipedia.org/wiki/XOR_linked_list

  • by cperciva on 1/30/17, 5:59 AM

    I feel I have to mention the algorithm for matching with mismatches which I published in my thesis (http://www.daemonology.net/papers/thesis.pdf), simply because it gave me a legitimate opportunity to use the phrase "Fourier Transform of the FreeBSD kernel".

  • by toomanybeersies on 1/30/17, 5:57 AM

    As basic as it is, and completely uninventive, I've always loved Dijkstra's algorithm.

    It was probably the algorithm that cemented my love of computer science, it's such an elegant solution to a problem and so simple once you understand it.

  • by daurnimator on 1/30/17, 5:15 AM

    The burrows-wheeler transform is pretty interesting https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf.... It's behind the bzip compression format.

  • by kul_ on 1/30/17, 4:41 AM

    I have never seen anything more elegant than Disjoint Set Datastructure https://en.wikipedia.org/wiki/Disjoint-set_data_structure

  • by jnpatel on 1/30/17, 5:10 AM

  • by ewwertee2454 on 1/30/17, 4:06 AM

  • by elihu on 1/30/17, 5:39 AM

    ROAM: Real-time Optimally Adapting Meshes https://graphics.llnl.gov/ROAM/roam.pdf

    Whitted's recursive ray tracing algorithm https://en.wikipedia.org/wiki/Ray_tracing_(graphics)#Recursi...

    PageRank

  • by 110011 on 1/30/17, 8:35 AM

    Here's a rather surprising one. There's an algorithm to generate a uniform random integer in the range 1..n with a KNOWN factorization. That means the algorithm is like a regular random number generator except it will also tell you how to factor it! Magic? yes! This always surprises people and i love results like this.

    Search for the paper by Adam Kalai on how to generate random factorized integers easily. It uses log^2 n primality tests an average. The result is originally by Eric Bach who managed it using only log n primality tests but using a more complex algorithm.

  • by gwicks56 on 1/30/17, 6:48 AM

    Diffie-Hellman

    One of those algorithms where you go "Shit so obvious and also so completely genius that I could never have thought of it"

    Also, the internet as we know it would not work without it

  • by aserafini on 1/30/17, 7:14 AM

    Ukkonen's algorithm for linear time suffix tree construction. Knuth called it 'the algorithm of 1973'.

  • by rbritton on 1/30/17, 5:29 AM

    Token Bucket. Very lightweight way to implement rate limiting.

    PHP implementation: https://github.com/bandwidth-throttle/token-bucket

  • by zelah on 1/30/17, 12:49 AM

    Linear Hybrid Cellular Automata: https://pdfs.semanticscholar.org/7835/161f253ab117a3666fa8e7...

    Parallelizable and efficient method for producing high quality pseudo random bits.

    Designed to achieve maximal period (with 500 bit state the period of repetition is one less than 2^500).

    Can be run backwards or forwards. Running it backwards undoes running it forwards and reproduces the pseudo random bits in reverse order.

  • by NTDF9 on 1/30/17, 1:54 AM

    Tomasulo's algorithm: https://en.wikipedia.org/wiki/Tomasulo_algorithm

    A modified version of it is used in most CPU register out-of-order execution

  • by gjvc on 1/30/17, 12:24 AM

    Great question. Without a doubt, my favourite is the Burrows-Wheeler transform (as used by bzip2)

    https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...

    https://www.youtube.com/watch?v=4n7NPk5lwbI

  • by akkartik on 1/30/17, 8:06 AM

    When I first read of HashLife I had the most extraordinarily vivid dreams of breaking all complexity barriers just by finding the right memoization scheme: http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...

  • by ryandrake on 1/30/17, 7:47 AM

    R* tree for indexing spatial data [1]. Also, if you enjoy spatial data structures, you can't go wrong with Samet's[2] _ The Design and Analysis of Spatial Data Structures_ and Applications of Spatial Data Structures_.

    1: https://en.wikipedia.org/wiki/R*_tree

    2: https://www.cs.umd.edu/~hjs/design.html

  • by pedrorijo91 on 1/30/17, 9:29 AM

    Randomized algorithms, specifically Monte Carlo (probably because it was the first I explored), have fascinated me since I met them. The idea of having a very simple/efficient method to look for a solution, instead of a very complicated one, and still be able to have a near optimal solution is amazing.

    (https://en.wikipedia.org/wiki/Monte_Carlo_algorithm)

  • by bananicorn on 1/30/17, 12:20 PM

    I really like Fleury's algorithm[0] - I used it to generate more efficient paths to draw on a canvas, for the purpose of displaying simple wireframe models. It may not be the most efficient, but I really like the simplicity.

    [0] http://www.geeksforgeeks.org/fleurys-algorithm-for-printing-...

  • by 110011 on 1/30/17, 8:25 AM

    There are a lot of great answers here. Let me add another one I really love: the Knuth Morris Pratt algorithm for string matching. There are many features about it I especially love. First of all it takes a simple idea (when a mismatch occurs it's often possible to shift the pattern a lot more than just by one position) and takes it to it's logical conclusion (that of defining and computing the so called border lengths of prefixes). Second, the analysis of the precomputation step (the border lengths) is tricky, and amortised, but plainly obvious once you see it.

    It shows the importance of making a good definition and thinking differently (for the run time analysis I thought for a while and failed to come up with an argument why it runs in linear time, but once you see it differently it's obvious :))

    I only recently had the chance to understand this algorithm. Here's a little (annotated) gist I made after understanding it: https://gist.github.com/quantumelixir/3c410dd4a0afe0f2514e0f...

  • by pmalynin on 1/30/17, 5:35 AM

    Number Theoretic Transform aka Discrete Fourier Transform.

    The algorithms for computing it are beautiful and have enabled much of the technology we see around us today.

  • by haidrali on 1/30/17, 7:34 AM

    I really like majority voting algorithm to get majority number in array which appears more then half of the elements, Its the most simplest and elegant algorithm i have studied

    http://www.geeksforgeeks.org/majority-element/

  • by drewmate on 1/30/17, 8:13 AM

    Ford-Fulkerson algorithm for finding the maximum flow across a graph: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorit...

    The algorithm itself is interesting enough, but when applied to bipartite graphs, you can solve some tough problems very efficiently. For instance, one of my favorites is how Santa could possibly match a million kids with a million different gifts in order to maximize happiness. It turns out you structure the problem as a bipartite graph with nodes on one side for gifts and children on the other, and Ford-Fulkerson can guarantee the best matching in polynomial time (no small feat, given how many possible combinations there are!)

  • by syntaxing on 1/30/17, 1:35 PM

    I've been diving into a bunch of the newer (computational) optimization algorithms but the old school ones that they teach in school is still extremely interesting and relevant to me. I've always been a huge fan of "Combinatorial optimization" [1]. I saw someone else mention this but the simplex algorithm is awesome as well! [2]

    [1] https://en.wikipedia.org/wiki/Combinatorial_optimization [2] http://gizmodo.com/5934150/the-algorithm-that-controls-your-...

  • by deepnotderp on 1/30/17, 5:51 AM

    Also, fft gets an obligatory mention

  • by jones1618 on 1/31/17, 5:40 AM

    Cuckoo Hashing: http://www.lkozma.net/cuckoo_hashing_visualization/

    "An elegant method for resolving collisions in hash tables... It has the rare distinction of being easy to implement and efficient both in theory and practice."

    It does an amazing job of packing values into N hash tables so there's very little dead space but lookups are very fast.

  • by ww520 on 1/30/17, 7:30 AM

  • by sAbakumoff on 1/30/17, 7:23 AM

    1. Karatsuba algorithm for fast multiplication. 2. Heap's algorithm for generating permutations.

    mostly because they clearly demo the power of human brain.

  • by jetti on 1/30/17, 4:31 PM

    My favorite is the Hindley-Milner type system algorithm: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_sy...

    It is what is used in ML based languages to infer type and apparently Haskell uses it a bit too

  • by taeric on 1/30/17, 6:40 AM

    Knuth's DLX algorithm. Uses what he calls dancing links to perform backtracking in basically constant space with a clever trick on doubly linked lists.

    He recently updated his implementation. Is very fun to read his notes on his implementation. In particular, he discusses things he had wrong.

    If you like poor JavaScript implementations, I can post mine again.

  • by Mr_P on 1/30/17, 5:06 AM

    Simplex. If you can transform your NP hard optimization problem into an LP, simplex can often work like magic.

  • by santaclaus on 1/30/17, 6:20 AM

    Kalman filter!

  • by notforgot on 1/30/17, 1:31 AM

    It looks like SWIM scales better than Raft. Are there well-known production systems that use it?

  • by rurban on 1/31/17, 2:58 PM

    Cheney's two finger garbage collector with forwarding pointers. Still beating every other GC out there by factor of 10, if you can afford 2x memory

  • by useanalias on 1/30/17, 5:55 AM

    Contrastive divergence for RBMs. Incredibly simple, but absolutely beautiful how it modifies the energy surface. Also, just in general a cool use of Gibbs sampling.

  • by nojvek on 1/30/17, 6:53 AM

    Convolutional neural nets and backprop. That stuff is magical.

    I also was fascinated as shit when I learnt about minimax and alpha beta search.

    Game theory and neural nets have always fascinated me.

  • by kovrik on 1/30/17, 6:09 AM

    HyperLogLog

  • by wfunction on 1/30/17, 7:41 AM

    I find the DC3/skew algorithm for linear-time suffix array construction mindblowingly clever!

  • by pizza on 1/30/17, 5:15 AM

    AIXI

  • by wwwhatcrack on 1/30/17, 8:20 PM

    I generally appreciate divide and conquer algorithms of any type

  • by jakeogh on 1/30/17, 7:58 AM

    Lamport's bakery algorithm is pretty neat.

  • by CalChris on 1/30/17, 6:23 AM

    Someone already mentioned Tomosulo.

    RSA.

  • by deepnotderp on 1/30/17, 5:51 AM

    Backpropagation

  • by chaotic-good on 1/30/17, 6:08 AM

    Sequitur