Completely true, and the problem is not just with education. As a field, computer scientists have fooled ourselves into thinking we can skip straight from math/theory to engineering. There's little science in computer science today.
The lack of scientific thinking affects every subfield of CS. A recent paper about computer security points out what should have been obvious: we've been trying to theorem-prove our way to scientific knowledge, but we need experiments and falsifiablily. microsoft.com/en-us/research…
Careful experiments can falsify vast bodies of assumed knowledge. My favorite is this paper arguing that the belief in the usefulness/necessity of distributed computing for processing big datasets is largely the result of poor experiments. usenix.org/system/files/c…
In machine learning, every other week there's a paper showing that accuracy numbers don't mean what we thought they meant, and that we have a way to go before we understand what's really going on in our architectures. We need more of these!
Why is this so pervasive in computer science? Why do we tend to jump from theory to engineering and skip experimentation? For that, we must turn to history! Stay with me. (And this was of course before my time; please correct me if I get details wrong.)
In the early days of computing, if you wanted to know how fast an algorithm is, you'd run it several times and compute the mean/variance of the running time. Then you'd have to do it on inputs of different sizes, and test different implementations on different machines.
All very laborious! You'd be lucky to have access to one computer, so you'd have to snail mail your colleagues to run it on their computers. And you'd end up with a mess of numbers; hard to know what's really going on. Maybe you'd try some regression modeling to make sense of it.
Along come the theorists, and point out that asymptotic complexity is a mathematical property of an algorithm in the abstract! You can compute it in your mind and end up with a single, beautifully simple mathematical expression. O(N log N). Boom. Done.
You don't need to touch real data or worry about machine details, and your answer won't change as machines get faster. You can easily predict how running time will grow as data gets bigger. How refreshing compared to the extraordinary messiness of the experimental method!
Analysis of algorithms was a major victory of theory over experiment — math over science — in the early days of computer science. And it wasn't the only one.
For over 2000 years, we believed that cryptography was a cat and mouse game between code maker and code breaker.
"Human ingenuity cannot concoct a cipher which human ingenuity cannot resolve." — Edgar Allan Poe (who was an amateur cryptographer!)
"Human ingenuity cannot concoct a cipher which human ingenuity cannot resolve." — Edgar Allan Poe (who was an amateur cryptographer!)
Advances in cryptography have indeed made venerable old ciphers look naive. Take "le chiffre indéchiffrable" en.wikipedia.org/wiki/Vigen%C3%…
When I'm invited to teach high schoolers about crypto, I love showing how to break this cipher. Takes under 5 minutes to explain & demonstrate!
When I'm invited to teach high schoolers about crypto, I love showing how to break this cipher. Takes under 5 minutes to explain & demonstrate!
Cryptography is no longer a cat and mouse game. It started to change in the 70s/80s. One big reason: we can now prove some things about cryptosystems. We still need to make assumptions about computational complexity—but not about the real world. Another huge victory for theory.
Of course, our theorems and proofs are about cryptographic algorithms and protocols, which are inherently idealized models. We can't mathematically prove things about the security of real systems, as pointed out in the paper earlier in the thread. microsoft.com/en-us/research…
So there we have it — we've seen the pendulum swing between theory and experiment in the history of CS, and it's clear that we need a healthy balance. As computer systems affect the real world and real people more and more, rigorous empiricism is becoming ever more important.
