Sort, Sweep, And Prune: Collision Detection Algorithms
- Lean Rada tl;dr: Sweep-and-prune is my go-to algorithm when I want to quickly implement collision detection for a game. I think it’s an awesome and elegant algorithm, so I wrote a post about it. This post is split into simple and sophisticated versions of the algorithm.featured in #542
Sleepsort: Sorting While Sleeping
- Animesh Chouhan tl;dr: “Sleep sort is a fun and quirky way to sort numbers. It was thought up by someone on 4Chan in 2011. Instead of the usual sorting methods, this one makes each number "sleep" for a bit before joining the sorted list. So, if a number is 3, it waits for 3 units of time before settling into its place.”featured in #510
Dynamic Programming Is Not Black Magic
- Quentin Santos tl;dr: Dynamic Programming is a method used to solve complex problems by breaking them down into simpler subproblems. Many common algorithms are the application of dynamic programming to specific problems, including Dijkstra’s path-finding algorithm. Quentin provides an introduction and examples.featured in #480
featured in #474
Abracadabra: How Does Shazam Work?
- Cameron MacLeod tl;dr: Shazam does the following to register a song: it calculates a spectrogram of a son, extracts peaks from that spectrogram, pairs those peaks up into hashes and stores the collection of hashes for a song as a fingerprint. Cameron discusses these in depth, as well as how Shazam recognizes an audio sample and matches it against its database.featured in #472
How Uber Computes ETA At Half A Million Requests Per Second
tl;dr: "A single trip usually takes around 1000 ETA requests.Yet computing ETA is a difficult problem. Because the distance between the source and destination is not a straight line. Instead it consists of complex street networks and highways." Engineers split a route into smaller partitions to find the shortest path amongst each partition, factoring in variables, such as traffic.featured in #470
Understanding DeepMind's Sorting Algorithm
- Justine Tunney tl;dr: DeepMind applied deep learning insights to develop a compact sorting algorithm. Their kernel function, move37, is a building block for sort3. This algorithm optimizes comparisons and swaps, achieving efficient sorting and the code examples demonstrate its evolution leading to branchless instructions and improved performance.featured in #424
Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning
tl;dr: “This article uses deep reinforcement learning to generate efficient sorting algorithms. The authors highlight the computational bottleneck faced when optimizing algorithms using traditional methods and introduce AlphaDev, a learning agent trained to search for correct and efficient algorithms.featured in #421
featured in #420
Beautiful Branchless Binary Search
- Malte Skarupke tl;dr: “I read a blog post that describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search?” Malte describes the algorithms mechanics.featured in #410