February 6, 2010
Books and such.
For years I’ve wanted to write a book. My friend Charles and I thought about writing a book on probability back when I was an undergraduate. Most recently I’ve been thinking about writing a computer science book which is an introduction to algorithms. This was spurred by my teaching exactly such a class this semester.
CS260 at the University of Alabama is entitled “Foundations of Computer Science”. This course is intended to be an introduction to the theoretical aspects of the field, ranging from analysis of algorithms to simple datastructures. This course is for second semester students, so unfortunately they’ve only had one semester of programming and don’t have a very strong math background. This means that we can’t do the more rigorous analysis of algorithms and fun proofs that would need things like counting and inductive proofs. So, I’ve decided to take a different tact. I’m trying to help them develop an intuition of the concepts by starting with the implementation of some algorithm (sorting algorithm, actually) and walking them toward a function which is computes how much work is required without actually doing the work. By then plotting these function they can get a visual representation of how much work is actually being done and see its relation to other mathematical functions. This has actually proven pretty effective at teaching asymptotics without actually teaching asymptotics.
Therefore, the book that I want to write is an introduction to theoretical computer science via empirical analysis. What if someone scoops me because of this? I don’t care. I think that this would actually help a lot of students and if I don’t get enough time to do it, then someone else should. So, I’m going to try to start putting the sketches of sections here. Eventually I’d like to set up a system like Bryan O’Sullivan had for Real World Haskell with random internet users being able to comment on parts of the books with suggestions. Stay tuned!
