Ask HN: What are your favorite algorithms? • Hacker News Board

Re: Ask HN: What are your favorite algorithms?

#71

Post by psi-squared » Mon, Jan 30, 2017, 11:20 AM UTC

daurnimator wrote: post #10

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

This is related to my current favourite algorithm: Because the BWT is closely related to the suffix tree of the original string, there's an algorithm to search for a substring of length 'm' in a BWT-ed string of length 'n' in O(m log n) time!

The one downside is that you have to pre-process the string, which takes O(n) time and between 5n and 9n space depending on exactly how you do it. But after that, you can do as many searches as you want practically "for free".

There's a paper outlining the various algorithms available here: (PDF) http://www.cosc.canterbury.ac.nz/research/reports/HonsReps/2...

Re: Ask HN: What are your favorite algorithms?

#72

Post by pkd » Mon, Jan 30, 2017, 12:17 PM UTC

DDR0 wrote: post #34

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 dupl…

This one is extremely popular in the interviewing circles thanks to CTCI.

Re: Ask HN: What are your favorite algorithms?

#73

Post by bananicorn » Mon, Jan 30, 2017, 12:20 PM UTC

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-...

Re: Ask HN: What are your favorite algorithms?

#74

Post by andreareina » Mon, Jan 30, 2017, 12:51 PM UTC

wmu wrote: post #53

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/wik…

I'm a big fan of Huffman coding myself, but Lempel-Ziv definitely gets points for being simple and intuitive.

Re: Ask HN: What are your favorite algorithms?

#75

Post by aryamaan » Mon, Jan 30, 2017, 1:25 PM UTC

kul_ wrote: post #7

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

+1. I was in love with union data structure as well when I get to know about them. And always used to feel good when I used to solve any algo problem with it.

Re: Ask HN: What are your favorite algorithms?

#76

Post by syntaxing » Mon, Jan 30, 2017, 1:35 PM UTC

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-...

Re: Ask HN: What are your favorite algorithms?

#77

Post by pwdisswordfish » Mon, Jan 30, 2017, 1:59 PM UTC

palashkulsh wrote: post #64

zelah wrote: post #32

Earlier quoted context omitted.

I vote twice for this one!

Any laymen explanation ? Not able to grasp the concept.

First you vote once, and then you vote again.

Re: Ask HN: What are your favorite algorithms?

#78

Post by The_Hoff » Mon, Jan 30, 2017, 2:57 PM UTC

wmu wrote: post #70

majewsky wrote: post #69

Earlier quoted context omitted.

> 2. The algorithm behind rsync. Do you mean the rolling checksum part?

All parts, I like how the simple parts were composed to built pretty complicated algorithm.

Yeah, I assume majewsky is wondering if you mean just the rolling checksum part because that's the most complex part. Rsync, as a whole, is certainly one of my favorites and the algorithm(s) it uses are some of the ones I most often call explicitly.

Re: Ask HN: What are your favorite algorithms?

#79

Post by taeric » Mon, Jan 30, 2017, 3:31 PM UTC

samcal wrote: post #33

taeric wrote: post #29

Earlier quoted context omitted.

Why "uninventive?"

I believe GP meant that picking Dijkstra's is an uninventive answer to the question of a favorite algorithm, since it's very well-known.

Ah that makes sense.

Re: Ask HN: What are your favorite algorithms?

#80

Post by 110011 » Mon, Jan 30, 2017, 4:08 PM UTC

nhaehnle wrote: post #62

Mr_P wrote: post #8

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

If you can transform your NP hard optimization problem into an LP, you have proven P = NP because LPs can be solved in polynomial time. That said, many combinatorial optimization problems that look quite similar to NP hard problems have very nice and efficient LP formulations, and for many NP hard problems, integer programming-based methods (which in the end mostly solve LP relaxations) are among the best algorithms.…

Adding to what you say, OP might have meant the use of LP solvers in branch and bound type algorithms to solve hard problems after recasting them as integer programs.