Even Strassen can be overly expensive for reasonably sized matrices. Almost all matrix multiplication algorithms have a threshold only beyond which do they use Strassen.

Although apparently that threshold can be lowered (http://jianyuhuang.com/papers/sc16.pdf), but even then it's a matrix that's several hundred columns by several hundred rows large.

Some CS classes explicitly use Strassen to teach the realities of asymptotic vs wall-clock time complexity, challenging students to come up with a hybrid matrix multiplication algorithm that performs the fastest and switches at the best thresholds of matrix size.

> To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc.

Which would have the positive knock-on effect of the textbook being sufficiently obsolete every year or so that the students could no longer trade it in for credit, saving the bookstores money!

More seriously, that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one. Teaching big-O analysis means the knowledge is timeless, which any good theoretical knowledge is, and moving more towards practice would force the professors to keep on top of the state of the art, and the state of the mainstream, of hardware design in addition to everything else they're doing.

> Which would have the positive knock-on effect of the textbook being sufficiently obsolete every year or so that the students could no longer trade it in for credit, saving the bookstores money!

That's naive. E.g. SIMD is here since a good time and going to stay. So are GPGPU, with now quite similar architectures for tons of chips.

And Computer Science can actually be about science for real computers, and computers are not 8086 nor PDP11 anymore, and have never been a turing machine. So there actually is some existing generic CS and ongoing research that cares about cache effects and so over. Maybe it is applied CS if you want, and some kind of pure CS should not care about that, but I really don't see what should be the criteria to decide which is what anyway, so IMO there should not be any (but I do not mean that all research should care about e.g. cache effects, just that it is not really useful to attempt to distinguish between those which do and those which don't).

We don't teach advanced math by only showing what was done at e.g. the beginning of algebra. Neither should we stick to only basic subjects in computer science.

> textbook being sufficiently obsolete every year or so

I wasn't very clear on that point, but didn't mean to suggest it be the same textbook. These other topics deserve courses and books of their own. The algorithms lecturer should be careful to emphasise the limitations of complexity theory though.

> that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one

Plenty of long-lived principles to be learned there, even if the particulars change over time. Caches are still going to be around in 10 years time.

Without knowledge of the hardware your software runs on you're likely to be one of those people who uses lists instead of vectors without really understanding the difference. Also, as other people said, the shelf life for that knowledge is actually pretty long. Hardware will always be your platform, no matter how many layers of abstraction you have in between.

> To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc.

They are in many places I'm aware of. At least, as an EE (at Stanford, but I've heard MIT and several others do the same), I had to take a digital system design class, but the majority of the class was spent on performance engineering. In fact, the very first (actual) project of the class was to take a 10-line piece of C code, which applies a simple filter in real time to a video, and make it performant. The initial code runs at around .5 FPS.

Our resulting performant code was, of course, many times larger (I think it might have been ~150 lines), but it ran incredibly quickly (110 FPS, iirc), by doing crazy compiler tricks and often calling ASM from within the C code, even though the asymptotic (big O) performance was exactly the same.

For context, this is not just a digital systems thing (my work is in mathematical optimization theory and my undergrad was in photonics and physics), but I do know that this class is not a requirement for CS since it's potentially too hardware oriented. The classes exist, but I'm not sure people are taking them.

> They are in many places I'm aware of.

Yes, sure. I hadn't meant to imply otherwise. The pure-algorithms lecturer needn't cover these other topics in detail in their course, but should be careful to emphasise the uses and limitations of complexity theory.

> this class is not a requirement for CS since it's potentially too hardware oriented

I don't see the sense in this. Computer scientists publish work on applying GPU acceleration, as they should - that's not electronic engineering work they're doing. We could quibble about whether it's computer science of software engineering.

> I don't see the sense in this. [...] We could quibble about whether it's computer science of software engineering.

I agree, I'm not sure why this is the case either, just my idea as to why it may not be a requirement. (Some part of the class does involve writing a good chunk of a 5-stage RISC processor based on MIPS, but this was still relatively straightforward with just a basic understanding of digital logic.)

I always loved my algorithms and datastructures professor talking about Brodal queues[0] - a datastructure named after him. They're super interesting from a theoretical point of view, but they're not useful for anything.

[0] https://en.wikipedia.org/wiki/Brodal_queue

That's a great example. Hadn't heard of it before.