I'm interested in a reply to iskander's question as well as some concrete examples of new "computer algorithms... frequently requiring years and millions of dollars".
Think of the algorithms sitting in the base band of your cell phone. They implement things like modulation, hand-offs, power control, etc. E.g. there is some algorithm that controls the transmit power of your device to maintain the minimal transmit power necessary to close the link to the base station while you move around, walk into buildings, etc. There's another algorithm that tries to optimize hand-offs as you go from one cell site to another. Etc. These algorithms are very expensive to develop because: 1) you need very expensive people (PhD's with decades of experience) to work on them; and 2) getting them right takes a ton of experimentation and tuning with real equipment in a variety of physical scenarios.
All of your examples sound like variations on fundamental CS problems, and most CS undergrads should have been exposed to them and to their solutions.
Are you saying industry is leaps and bounds ahead in the fundamentals of CS theory? Or just that there is a lot of vendor specific detail in the hardware and infrastructure? Because the latter is not CS.
They're not just variations on fundamental CS problems because the complexity of the problem is dominated by physics + hardware + infrastructure. E.g., while most CS undergraduates are exposed to control theory, a power control loop isn't a simple application of a controller. It has to deal with the physics of signal propagation, knowledge of the kinds of environments users encounter, the characteristics of the underlying radio, and the nature of the network infrastructure. All that insight and experimental validation is ultimately packaged as an algorithm (although a very specific and detailed one).
To analogize to another domain: a power control loop in a cell phone base band is as much "just a variation on fundamental CS problems" as is register allocation for a hairy architecture like x86. Yes, graph coloring gives you a conceptual framework to start with, but that gets you 10% of the way to a usable solution.
You seem to be saying that it's "fundamental computer science" to be aware of a problem and the naive ways to solve it, but not fundamental CS to know what methods are actually usable in the real world. That definition may have its merits, but is certainly not appropriate to use in a patent law discussion.
Yep, examples would be interesting. There are counter examples - like the open Opus audio codec, which was developed by collaboration of various engineers and which is state of art precisely because they weren't burdened by stupid patenting issues, and could instead concentrate on creating a beautiful technology.
How is it a counter example? Open Opus is built on patented technologies that are licensed royalty free by the original inventors (Broadcom, Xiph.org, Microsoft, etc). It certainly wasn't cheap to develop--the development cost is just being subsidized so the end result can be given out freely.
"Patented" doesn't equal "was expensive to develop".
In the context of codecs we're actually seeing how it prohibits improvements of technology.
Broadly speaking (i.e. I'm sure there are counter-examples, but they are not significant in the big picture), people didn't patent compiler technology, and we had great progress in compiler technology.
People didn't patent database technology and we had great progress in database technologies, from both academic research and competition.
People didn't patent word processing technologies so that Google can re-implement Word functionality in the browser because none of the fundamental techniques have been patented. Again, lots of progress from competition.
For whatever reason, audio and video codecs are heavily patented and the technology is ludicrously outdated compared to what it could have been if we had progress from competition or academic work of free software implementations because the patents cover basic ideas in compression so no-one can build on them and patent holders have no incentive to improve the technology because it's much easier (and more profitable) to just collect royalty checks.
However, developing video codecs isn't any more expensive than developing databases or compilers or word processors.
See e.g. h264 encoder which is an open-source effort by few amateurs that is widely regarded as being of better quality than commercial offering costing thousands of dollars (because of patent monopolies, not because they were so expensive to develop).