But this isn't a comp sci book really since it doesn't actually cover any comp sci topics such as the analysis of computer programs, algorithms and data structures.
It's no use to know about algorithms and complexity if you only know how to sort punch cards as that isn't a modern day computing task.
A computer sceince background inherently implies software development background. This also includes an understanding of low level implementation and backing hardware that makes computation possible so you may understand the limitations of the hardware and how to engineer within those constraints.
An algorithm that takes infinite time for 1 instruction is O(1) and still constant time. An algorithm that takes infinite memory for every run is still a constant memory complexity. Knowing this tells you nothing about how implementable these algorithms are and thus a focus on only this algorithm and datastructure portion of computer science is useless without practical applications and an understand of how to go about implementing and discovering your own data structures and algorithms for real life tasks.
The entire field of theoretical computer science stands as a counterexample to your comment. Computer science is not about software engineering.
I don't know where an uncomputable algorithm would be useful.
I do know that you cannot possibly start a student out on a plane of the purely theoretical as they cannot see the value of what they are learning, they cannot understand the implications of the material, and frankly they won't remember it if they don't need it. To their minds, they don't need it if they haven't used it. It can be JFM (Just Fking Magic) to them if they haven't seen a case where it has improved their own algorithms. They will also not really understand how it works with no implementation. It is impractical to say the least.
Theoretical computation is a higher level topic then real computation topic. In the same sense that you start math with addition, subtraction, multiplication, and division you should start out computer science with implementation.
However, this does not mean complexity theory is useless; it still informs us of what computers can and cannot efficiently do. It marks the limits of feasible computation.
> I don't know where an uncomputable algorithm would be useful.
Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant.
As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten.
My point, as stated in another comment of mine in this thread, is that it is not necessary that a "true computer scientist" know anything about low-level computer details. I suspect this holds true not only for theoreticians, but also many systems builders (like in distributed systems and such). So, having a intro course focusing on low-level details as the main component will not necessarily provide a good introduction to computer science.
I do not think this is a correct statement from what I've seen.
> As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten.
If the course is organized correctly the experiance can be magical. You're pulling the curtian on the the giant talking head. You're showing the students how everything works and you should do this directly. Like all teaching the student needs to THINK they have been the ones to discover something while in reality the teacher is supposed to have errected an artificial situation where in this was the case.
You don't start them off with bits right off the bat although that is one approche (That is extremely successful: see NAND 2 Tetris). Like I said in my other comment you state them off with a broken machine. You give them an artifical reason to continue. "If you want to get a grade you have to open up this machine and, with me coupled with some hand holding, diagnose the problem." That gives them a reason to learn about the different parts of the computer. That errects a situation where they FEEL that have found something that they weren't meant to. They've explored something when in reality it was all, as someone smarter then me once said, a "Head Fake". Get them looking at a nearer goal and they'll start dreaming of further ones.
All I'm pushing back is on the idea that learning the intricacies of modern computing is necessary for being good at computer science.
EDIT: And wrt complexity theory and computability: there is a subfield of mathematics called computability theory that concerns itself with various notions of what is and isn't computable. Complexity theory concerns itself instead with what is efficiently computable; the problems it considers are already computable.
Cryptography isn't Computer Science. It uses some things that Computer Science developed but it isn't Computer Science. It's applied Math.
If Cryptography is in CS then Nuclear Reactor Operations is in CS. NRO uses computers for monitoring systems and develops algorithms to detect certian... ahm... undesierable states. That doesn't mean we should move a reactor into the CS building at every college near you (although I'd love to work on one eventually, sounds like cool work).
Academics may think that crypto is a CS field but the work involved has absolutly nothing to do with CS. For example, all cryptographic functions can be implemented in hardware. If you are building a cryptographic function in hardware, you're not part of the Electical Engineering department or the Mechanical Engineering department you are still in the Math department because all you're doing is implementing an abstract design.
(Insert unintelegable "get off my lawn" statement)
I am not sure what your idea aof cryptography is, but crypto relates to the most basic of questions about computation: what is and isn't efficiently computable, that is, P ?= NP.
You do realise that the origin of the field of Computer Science lies in mathematics, specifically Turing's work, right? By your argument, the entire field of Theoretical Computer Science is ... not a part of computer science. Some how, I think that that's not quite right.
For example, lets say that a new computer could switch places of two blocks of memory in constant time no matter their sizes. That would completely revolutionize computer science since many of our old results hinges on the fact that moving memory takes linear time.
Of course, the truth of this thesis has been called into question with the advent of quantum computers, but it holds otherwise.
> An algorithm that takes infinite time for 1 instruction is O(1) and still constant time.
> An algorithm that takes infinite memory for every run is still a constant memory complexity.
None of these are true.
Can you give an example of such an algorithm? My understanding of an algorithm is that it must terminate in a finite amount of time, but maybe you have a different definition of an algorithm
Any practical algorithm yes. Any theoretical algorithm no. This is where the will it hault questions come from. Check out Ackerman's function as a good example that we aren't sure if it will terminate. It is still extremely interesting from an algorithms analysis perspective but not from a CS (as I use it) perspective.
Also I'm not specifically talking about algorithms. I'm talking about flaws in O() notation in practice. It is easy to make something look fast in theory when it is far slower in practice.