KnowSoda
TechnologyComputing
Algorithms: fun facts and quiz
The essentials in 7 ideas, with fun facts, an illustrated story and a quiz to see how much you know.
The essentials
What an Algorithm Is
An algorithm is a set of clear steps for solving a problem, like a recipe. Computers follow algorithms, and so do people tying their shoelaces.
Key fact
The word comes from al-Khwarizmi, a 9th-century Persian mathematician.
Searching
To find a name in a sorted list, don’t start at the top: open the middle, see which half it’s in, and repeat. That’s binary search.
Key fact
Binary search finds one name among a million in about 20 steps.
Sorting
Sorting puts things in order. Simple methods compare neighbours and swap them; faster ones split the list, sort the parts and merge them back.
Key fact
A computer can sort a million items in a fraction of a second.
Recommendations
Streaming and shopping apps use algorithms to guess what you’ll like, based on what you and people like you chose before.
Key fact
Recommendations can trap us in a bubble of more of the same.
Fast & Slow Algorithms
Two algorithms can solve the same problem at very different speeds. As the input grows, a smart method can be millions of times faster than a naive one.
Key fact
Computer scientists describe speed with “Big O” notation.
Finding the Best Route
Map apps find the quickest route with shortest-path algorithms, like one Edsger Dijkstra invented in 1956, reportedly in about 20 minutes.
Key fact
Dijkstra designed it without pencil and paper, at a café.
Hard Problems
Some problems have no known fast algorithm. Finding the shortest trip that visits many cities, the travelling salesperson problem, gets explosively harder with each city.
Key fact
With 20 cities, there are over 60 quadrillion possible round trips.
Fun facts
Euclid’s method for finding the greatest common divisor is over 2,000 years old, and computers still use it.
Guessing a number from 1 to 1,000 by halving the range each time never takes more than 10 guesses.
Python’s built-in sort, Timsort, mixes two methods: merge sort for big runs, insertion sort for small ones.
Netflix once offered a 1 million dollar prize for improving its recommendations by 10%. A team won it in 2009.
Sorting a million items by comparing every pair takes about half a trillion steps; smart methods need about 20 million.
UPS plans its delivery routes to avoid turning across traffic where possible, saving fuel and time.
Proving whether problems like this can ever be solved quickly comes with a 1 million dollar prize.
Story: The Man Who Became a Word
The Man Who Became a Word
Baghdad, around 825. Scholar Muhammad al-Khwarizmi writes a book on calculating with the Indian numerals, zero included.
Three centuries later it’s translated into Latin as “Algoritmi on Indian numbers”. Algoritmi is simply his name, spelled the Latin way.
Readers took it for a word for step-by-step calculation. “Algorism” slowly became “algorithm”, so every recipe for a computer carries his name.
True or false?
Tap your answer to see if you got it, and why.
-
Question 1 of 10
An algorithm is a defined sequence of steps.
Show the answer
True. Clear enough that anyone, or anything, can follow them.
-
Question 2 of 10
Binary search needs the list to be sorted.
Show the answer
True. Otherwise you can’t tell which half to keep.
-
Question 3 of 10
Some sorting methods split a list into smaller parts.
Show the answer
True. Like merge sort and quicksort.
-
Question 4 of 10
Recommendation algorithms learn from past choices.
Show the answer
True. Yours and those of similar people.
-
Question 5 of 10
Two algorithms can solve the same task at very different speeds.
Show the answer
True. The method matters more as the task grows.
-
Question 6 of 10
Map apps use algorithms to find routes.
Show the answer
True. Weighing distance, traffic and road types.
-
Question 7 of 10
Some problems have no known fast algorithm.
Show the answer
True. Nobody has found a quick method for them yet.
-
Question 8 of 10
Every algorithm has to be written in a programming language.
Show the answer
False. A recipe written in plain words is an algorithm too.
-
Question 9 of 10
Binary search checks every item one by one.
Show the answer
False. It halves the list at every step.
-
Question 10 of 10
All sorting methods are equally fast.
Show the answer
False. Some are far faster on big lists.
Keep going in the app
KnowSoda learns what you know and brings back what you’re about to forget. Algorithms has 6 more ideas at the Advanced and Expert levels.
Sources
- Khan Academy — Algorithms
- Encyclopaedia Britannica — algorithm, al-Khwarizmi
- Clay Mathematics Institute — P vs NP problem
- Communications of the ACM (2001) — interview with Edsger Dijkstra
- Brin & Page (1998), the anatomy of a large-scale hypertextual web search engine
- Cloudflare — LavaRand: randomness from lava lamps
