Browse

Why sorting gets slow so fast: bubble sort versus merge sort and n log n Two sorting methods can both be perfectly correct and still differ by a factor of 25,000 on a big list. Race bubble sort against merge sort on the same… Computing3 min read2 Nov How your phone finds the quickest route: Dijkstra's shortest-path algorithm Your phone finds the fastest route across millions of roads without trying them all. The trick is a rule Edsger Dijkstra devised in 1956: always finish the… Computing3 min read30 Oct Why swapping cards at random is not a fair shuffle: Fisher–Yates and the 27 paths Shuffling three cards by swapping each one with a random card from the whole row looks fair, but it is not. It makes 3 × 3 × 3 = 27 equally likely paths for… Computing4 min read20 Oct How to find one name among a billion in 30 looks: binary search Pick a number from 1 to 1,000,000 and you can find it in at most 20 yes-or-no questions. The trick is binary search: look in the middle of a sorted list, throw… Computing4 min read15 Oct Why common letters get short codes in a ZIP file: Huffman coding ASCII spends 8 bits on every letter, whether it is a common e or a rare z. In 1951 a graduate student, David Huffman, found a way to give frequent symbols… Computing4 min read12 Oct How a Bloom filter says "definitely not" using just a few bits How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add… Computing3 min read3 Oct How one extra digit on your bank card catches your typos The last digit of your bank card number isn't part of your account. It's a check digit, computed from the other fifteen by a recipe an IBM engineer patented in… Computing5 min read27 Sep How computers fake grey using only black and white dots Old Mac screens, cheap printers and some modern games can only show two colours: black and white. Yet they still draw soft shadows and smooth skies. The trick… Computing5 min read26 Sep