Speed Thrills: Visceral Demonstrations That Get Students Excited About Efficient Algorithms Conference: This work is, as of April 2026; ; unpublished.
Alistair Moffat, David Hawking · 2026
Read Speed Thrills: Visceral Demonstrations That Get Students Excited About Efficient Algorithms Conference: This work is, as of April 2026; ; unpublished. by Alistair Moffat, David Hawking (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-08938.txt.
Introduction
Moffat and Hawking tackle a teaching problem in data structures and algorithms courses: how to make students feel why efficient methods matter. They present two plain problems, each with a chain of improvements to a basic method, so runtimes fall from days or even years to a few seconds. Calling such chains thrills of algorithms, they argue that the dramatic drop lands viscerally in a way lectures rarely match. They frame the demonstrations as classroom material for motivating algorithm design.
Catalog record
| CREATOR | Alistair Moffat, David Hawking |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57081 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.08938
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Speed Thrills: Visceral Demonstrations That Get Students Excited About Efficient Algorithms Conference: This work is, as of April 2026; ; unpublished. Alistair Moffat, David Hawking Abstract . We address the problem of motivating students in Data Structures and Algorithms courses by presenting two simple problems that each have a series of improvements to a basic algorithm, leading to spectacular decreases in runtimes. Coining a new term, we refer to such sequences as being “ thrills of algorithms ”. Seeing runtimes drop from an estimate of days (or even years) to just a few seconds has a visceral impact which conveys the importance of efficient algorithms in a way unlikely to be forgotten. The demonstrations are particularly compelling because they can be performed live in class on the lecturer’s laptop. To assist staff teaching such courses we provide detailed pseudocode descriptions and complexity analyses for the various methods, and can supply implementations on request. † † cc-license: by 1. Introduction One of the most important lessons a budding computer scientist must acquire is the knowledge of algorithmic problem solving, and an understanding that a “correct” solution to a computational problem may not necessarily be a “useful” one – that a program that requires aeons to declare a solution is not any better than not having a program at all. This lesson is often associated with courses in data structures and algorithms, and presented via mathematical definitions of “big Oh” and similar notations, topics which students can find dry and challenging. Our experience through several decades of such subjects is that this lesson benefits enormously from being made visceral, and experienced via the senses as well as by logic. To this end we routinely make use of two simple computational problems that have a number of attractive properties: both have simple descriptions that even novice programmers are able to grasp and then consider solutions to; both have obvious solutions that are viable when tested at small scales, but with execution times that grow rapidly when the problem size is increased; and both have a range of solutions of increasing asymptotic efficiency that can be understood with only a little more effort. In writing this paper we pondered a suitable collective noun for a such a hierarchy of algorithms all addressing the same problem, and eventually settled on “thrill”, as in, “ a thrill of algorithms ”. In particular, we argue that being able to present a sequence of approaches provides the visceral understanding that is so important. In the “normal” world, a breakthrough that saves 50 % of some resource would be a remarkable improvement. For example, think of the recognition that would be showered on an aeronautical engineer if they were able to save 50 % of the fuel cost of intercontinental flights. Indeed, even a 5 % savings would bring substantial professional recognition. Now consider a computational task of size n and a straight-forward approach to solving it. Imagine executing that program on problem instances of increasing size with you delivering some pre-planned commentary while your students watch: “let’s try n=1000 , wow, that was fast; let’s try n=2000 , still fast; n=4000 , was that a very small ‘blink’ occurred before the answer came, maybe we can try and measure the time taken.” Then imagine enabling some kind of automatic timing, and starting a spreadsheet to construct a record of the running times as n is increased. And segueing from measurement alone, into predictions while you do so. Now suppose that the n=10{,}000 instance is measured as requiring 0.03 seconds; and that when you get to it the n=100{,}000 instance takes around 3 seconds, which 100 times longer. Now you initiate the n=1{,}000{,}000 execution, and then continue with the planned script while it is running, using the spreadsheet to analyze the running times observed so far, explaining as you go that once you have a model the accounts for the observations to date, you’ll be able to start making predictions with it. That “sales patter” needs to take around 5 minutes, and needs to conclude that the n=1{,}000{,}000 run will take something like 300 seconds (which is the 5 minutes you have been talking for, of course). If you get the timing right the n=1{,}000{,}000 run will finish right on cue when you need it, and take 100 times longer than the n=100{,}000 one. Figure 1. One of the authors reaches the visceral “tadaa” moment in a lecture when a “flight from Melbourne to Shanghai” (Repeats Method 1, n=10^{7} , m=100 , extrapolated to take nine hours based on an execution of n=10^{6} needing 320 seconds, see Section 3 ) is accomplished in just three seconds using a better algorithm (Repeats Method 2). Then initiate (why stop at 1{,}000{,}000 !) the n=10{,}000{,}000 execution in the terminal window, and return to the spreadsheet. Based on the observation already accumulated, it should now seem plausible to expect a problem of that size to take 100 times 5 minutes, with that estimate allowing you an exclamation of “wow, gee, that’s 9 hours, that’s how long it takes to fly from Melbourne to Shanghai”. And you then explain that you need to control-C the execution, because no-one in the room wants the lecture to last another 9 hours. And then, still in the spreadsheet, point out that invoking another factor of ten on n leads to another (predicted) factor of 100 on the execution time, at which point you can pretend to pull your hair out and cry “gee, wow, that would be more than a month of computation to handle n=100{,}000{,}000 , I guess no point starting that one, none of us want to wait that long”. Followed by “and, guess what, if n is a billion it’s going to take 10 years. Some of you might still be at the University then, but I probably won’t be!” Then imagine switching to a different mechanism with “here’s a different program I prepared earlier, I’m not going to tell you yet how it works, you just need to trust me”, and asking the class, “do you think this new program will be able to solve an n=10{,}000{,}000 instance in less than an hour? “Could it be 9 times faster than the one we just saw?”, you say. “That would be like flying from Melbourne to Shanghai in just one hour, wouldn’t that be amazing!” Then keep right on going: “what about less than 10 minutes? Do you think that might be possible? Less than 1 minute?? Will you give me a standing ovation if I can do n=10{,}000{,}000 in less than a minute???” Well, with the right choice of “before” and “after” algorithms, you’ll get your standing ovation for sure, because the difference between an O(n^{2}) algorithm (which is what the first one is, obviously) and an O(n\log n) algorithm is so compellingly substantial that the latter will – even allowing for a likely higher constant coefficient – result in an execution time that is not just certainly less than a minute for n=10{,}000{,}000 , but quite probably less than ten seconds . Finally, you tell the students: “by the end of this subject you’ll know how I did that, you’d better keep