ICP for 3d point cloud alignment
Ask HN: What's your favorite elegant/beautiful algorithm?
91–100 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#92Interpolation search [1], which allows you to search a sorted array in O(log(log(n))) time, assuming its elements are uniformly distributed (for instance, you are searching a sorted array of hashes.)
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#93K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose…
I prefer mean-shift for it's simplicity, as it even creates it's own clusters.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#94The "FRAIG" algorithm is pretty cool. To find equivalent nodes in an And/Inverter graph (e.g., a hardware circuit), it operates by... (1) simulating the graph on random numbers to identify nodes that might be equivalent (this can be done with huge parallelism by using wide, bitwise and/not operations) (2) using SAT to determine if these candidates really are equivalent (3) building a new network that canonicalizes al…
more like a reduction to SAT than a standalone algorithm though.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#95Earlier quoted context omitted.
What I like about Dijkstra's algorithm is not that you can calculate the shortest path between two nodes, but that you can calculate the shortest path from one node to every other node, and do it one pass in O(n) time. I'm not sure it's at all obvious that it should be possible to do that.
>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…
You are, of course, correct. That was sloppy writing on my part.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#96It would be hard to beat Floyd–Warshall algorithm. Think about the problem of finding shortest paths between all pairs of nodes in graph. Sounds trivial? Would you believe if someone told you it can be done in literally 5 lines of code? When I saw that for the first time I was in the disbelief. The elegance comes from these fact,
- Very non-trivial problem
- Just 5 lines of code
- Probably the most language agnostic algorithm
- Outrageously fast if graph fits in cache
- You can explain it to even non-programmers
- You can wear it on T-Shirt
- Doesn't require any fancy sub-algorithms, libraries or whatever
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#97Fenwick Tree (Binary Indexed Tree)
cool data structure indeed.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#98Gaussian integration. You might have heard of "2nd order" or "4th order methods to calculate an integral. This means that the error drops off with the number of sampling points like N^-2 or N^-4, respectively. But Gaussian quadrature has spectral accuracy, which transcends this measure. Error goes down like an exponential of N. Another neat feature is polynomials of degree 2N-1 or less are integrated exactly with thi…
what?? the solution set is infinite, how does it choose?
Right!? Such is the magic of orthogonal polynomials. If one chooses the integration grid to lie at zeros of the appropriate orthogonal polynomial, information is gained.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#99Boyer-Moore substring matching
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#100[deleted]