One of my favorite recent books is Street Fighting Mathematics: a collection of techniques and heuristics for rapidly and roughly estimating the solutions to problems that may be very difficult to solve exactly. The book is important because estimation is incredibly useful for understanding the world and because our education system does not do a very good job in teaching it. I think the tacit assumption is that people will pick up street fighting methods on their own.
During the last couple of years I’ve started to wonder how to teach street fighting computer science. The need for rapid estimation comes up all the time, for example, when studying operating systems. How long does it take to read all of a 2 TB hard disk? How long does it take a packet to cross a data center, a city, or a continent? How big is a 36-bit address space? These are very simple problems compared to the ones that Mahajan tackles but even so, not everyone can quickly rattle off approximate answers.
Mahajan’s book is structured around a collection of general-purpose techniques:
- Dimensional analysis — In CS terms, the universe has a type system and it can be exploited to make inferences and catch mistakes.
- Easy cases — A correct solution must work for all input values — so set parameters to zero, one, infinity, or whatever makes the math simple.
- Lumping — Use discrete approximations (perhaps a very coarse one, such as invoking the trapezoid rule with just one trapezoid) instead of calculus.
- Pictorial proofs — Use visualization to gain intuition into problems who symbolic forms are hard to understand.
- Taking out the big part — Split an answer into a big part and a correction; don’t even compute the correction unless more precision is needed.
- Analogy — Find an analogous but simpler problem, solve it, and project the result back to the original problem.
These apply to street fighting CS just as well as street fighting mathematics. For example, taking out the big part is something we do all the time when determining efficiency of algorithms. On the other hand, the bulk of the technical content in Mahajan’s book is a collection of calculus-based problems about the physical world. These aren’t really where we want to be spending most of our time in a CS course (especially if everyone else’s calculus is as rusty as mine). What might we cover instead? Here are a few ideas:
- Powers of 2 and 10 — This is basic, but all CS folks need to be able to rapidly convert any power of 2 up to about 40 to the nearest (or at least a close) power of 10, and vice versa. Similarly, converting between hex and binary should be quick.
- Important constants — These are mainly sizes (hard disk, CD/DVD, RAM on a PC and smartphone, various caches, etc.), times (packet transmission, cycles, seeks, interrupt latencies, human perceptual constants), and rates (signal propagation in copper and fiber, bandwidth of various interconnects, power consumption of common devices, etc.). Here’s a nice list of times. A few important ASCII codes (such as those for 0, A, and a) should be memorized.
- Counting arguments — The pigeonhole principle and such.
- Lopsided distributions — For example when estimating flight time through a network using measurements, all outliers will be on one side.
- Rules of thumb — Amdahl’s Law, Occam’s Razor, etc.
Next, we want a collection of diverse example problems to work out. Probably these will mostly come from people’s everyday experience making computer systems work, but we can also draw on:
- Books by Martin Gardner and A. K. Dewdney (Magic Machine, Tinkertoy Computer, Turing Omnibus, etc.)
- Collections of CS interview questions including How Would You Move Mt Fuji?
- Bentley’s essay The Back of the Envelope, from CACM and Programming Pearls; also The Envelope is Back
Basically I’m just fishing around here to see if this idea has legs; I’d appreciate feedback.
6 responses to “Street Fighting Computer Science”
“rapidly convert any power of 2 up to about 40 to the nearest (or at least a close) power of 10, and vice versa”
Huh. I’ve just memorized the powers of 2 automatically over time (up to 32, from thereout I don’t have the exact numbers), so converting them to a 10-power isn’t hard. If you are good at doubling numbers in your head (and there’s no reason why you shouldn’t be) you probably don’t even need to memorize anything but some markers (256, 65536, 16777216 (which is a lovely number), 4294967296), especially if you only need it approximately.
I don’t really ever do the reverse (from 10-power to 2-power) without a computer nearby, but it’s really simple since 10 log 2 ~= 0.3 (which is one of those constants everyone should know). So 10^20 = 2^(20/0,3) = 2^(200/3) ~= 2^67. Just take the 10-power, divide by 3 and shift the comma. The inverse operation if you haven’t memorized the 2-powers is left as an exercise…
The basic physical constants are a good idea. Too much optimization focuses on “faster” instead of working towards a specific goal, so someone can waste untold amounts bumming cycles out of a loop for a program that is now and always will be I/O bound. Too many programs are too slow to be comfortably used by humans because the designers didn’t keep response times in mind every step of the way, so they made it very expensive to fix.
Fast approximate mental calculation is of special importance to CS practitioners because there is a natural tendency to rely on computers for all calculations (after all, you’ve almost always got one handy). This is bad because calculators are too fast — in a flash, they can give you wrong answers that are implicitly trusted, and you can calculate anything you want. Doing it in your head gives you a better appreciation for correct and incorrect calculations and forces you to focus on the big factors, not the 17 digits after the comma. Obviously I’m not saying you should do everything in your head when you do have a calculator handy, but merely being able to helps. Plus, it’s fun to learn because you can learn and apply all sorts of algorithms (or “tricks” if you prefer) to speed up calculation — there are plenty of books on this. Think of it as optimizing for a curious bit of hardware.
This sounds like an excellent book idea, but I think that it does not work as a course.
Although you may know why these tidbits are extremely useful to have readily accessible, I’m not sure they will stick without the context of experience. Students will normally not have enough experience, whereas someone seeking out and reading a book will.
As for content: Definitely need to include the Pareto Principle. You might also want a section on social issues related to CS, such as “The Mythical Man-Month” and “Pournelle’s Iron Law of Bureaucracy.”
I like the idea. In my courses (networks and graphics-based), I tend to be both conceptual yet very practical for what I attempt to teach the students. Whenever possible I try to interleave some of the practical knowledge suggested in this post into what they’re doing in these courses. It seems very valuable if you’re really trying to solve problems.
The street fighting ideas might give students a basis to conceptualize and think about the solutions to problems before sitting down and typing up a prototype.
Where can I preorder the book? 🙂
Some of the original items can translate well.
Dimensional analysis — This kind of works directly for CS. At least the idea that most estimation problems can be expressed as a single product of terms.
“Taking out the big part” & “Easy cases” — These can also be phrased as “ignore the corner cases”
Lumping — Hard code things, Look-up tables,
And given that we have computers available, things like successive approximations (light weight GA and optimization techniques) and time step simulations (e.g. for queuing theory) should be covered. Also, I think some of the same mindset can be used not just for estimation (a symbolic answer to “can this work”) but for experimental prototyping (an empirical answer).
If you succeed in coming up with street-fighting problems for your courses, it would be a great idea to make use of the original book’s Creative Commons licence and write a “remix” for CS students/educators to use. I’ve been wondering if the same could be done for MechE problems…