September 17, 2007
While researching Classic Computer Science Puzzles, our CEO Scott Stanfield turned me on to A.K. Dewdney's The New Turing Omnibus: 66 Excursions in Computer Science.
This is an incredibly fun little book. Sure, it's got Towers of Hanoi, but it's also got so much more:
The book is designed to appeal both to the educated layperson and to the student of computer science. But how is that possible? The answer lies in the variety of treatments as well as topics. Some of the topics are inherently easy or I have been lucky enough to stumble upon just the right expository mechanisms. Some of the topics are inherently deep or complicated and there is no way around a certain rigor, including occasional mathematical symbolism.
For students of computer science, the 66 chapters that follow will give a sneak preview of the major ideas and techniques they will encounter in their undergraduate careers and some they may only encounter as graduate students. For professors of computer science, my colleagues, the 66 chapters will amount to a sneak review. Trying to remember how the Boyer-Moore string-matching algorithm went? It's right there in Chapter 61, Searching Strings. As for your lectures, if you like to deliver your own material this book may be what you've been looking for.
At one end of its spectrum of uses, The (New) Turing Omnibus may be ideal in bringing students from diverse backgrounds "up to speed." At the other end of the spectrum, you retain creative control but draw a few (or many) of your lectures from this book. Finally, for educated laypersons, the book provides a brief roadmap of computability.
I have no idea why I hadn't heard of this book, originally published in 1988 and updated with a second edition in 1993, until now. The New Turing Omnibus is is probably the single closest published equivalent to what I do on this very blog. It's a grab-bag of computing topics. Each chapter is the equivalent of a short blog post examining a particular topic, peppered with tables, diagrams, and illustrations. And the topics aren't presented in any particular order. Browse and find something you like; discard the rest. Here's a short excerpt from Chapter 33, Shannon's Theory - The Elusive Codes:
A complete table of contents for all 66 chapters of The New Turing Omnibus is enumerated at Everything2. I think there's a very high probability that if you enjoy reading this blog on a regular basis, you'll also enjoy this remarkable little book. As promised, it's a great way to keep practicing the fundamentals for professionals:
Bert Bates (my co-author) is a blackbelt level go player, one of the best amateur players in the state. But when a visiting expert-- four belt levels above Bert-- showed up at the local go tournament, Bert was surprised to see the guy reading a book on fundamental go problems that Bert had read much earlier in his learning. The expert said, "I must have read this at least a hundred times. My goal each time is to see how much more quickly I can solve all the problems in the book than I did the last time."
Some of the best athletes never forget the fundamentals-- whether it's Tiger Woods practicing the basics, or a pro basketball player working on free throws. A good musician might still practice arpeggios. A programmer might... I don't know, actually. What would be the fundamentals that a good programmer might forget? I'll have to think about that one.
But it's not just a book for programmers; it's also got a broad, down-to-earth appeal. It's an intriguing collection of thought puzzles for laypeople with at least a passing interest in the field of computer science.
If you'd like to see more, you can browse through a few pages of the book at Amazon. A few more pages are available in Google books, but beware the randomly inserted "copyrighted image" placeholder instead of the many illustrations and diagrams throughout the book.
Posted by Jeff Atwood
I'm really liking the projecteuler.net link that someone posted in the previous thread.
I can work out clever answers, or I can be lazy and bruteforce.
Sales are up 24,367%, LOL
The power of Internet blog advertising. You should get a kick-back from the publisher/author.
As a (black-belted?) go player I must protest! We do not use belts, although kyu / dan ranking is used. :)
What would be the fundamentals that a good programmer might forget?
KISS. RTFM. PEBKAC. DRY. If it ain't broken, don't fix it. Cheap, fast, accurate; pick two. If your program is idiot-proof, they'll find a better idiot. Any piece of software reflects the organizational structure that produced it.
"The power of Internet blog advertising. You should get a kick-back from the publisher/author"
But if he were, we could no longer trust his recommendations.
A good book is always welcome but a good blog generates great discussions! :-)
If you make an idiot-proof program, _you_ probably won't be able to use it.
You got me thinking about what are the programming fundamentals. It's not like Go where you are refining your skill at a single task over and over. Programming is funny since once you solve the problem there is no need to solve it again if you are a subscriber or DRY.
Furthermore, if you are a subscriber of DROPE (Don't Repeat Other People Either - OK, I just made that up) you shouldn't have to solve a problem that anyone else has either. So what's the fundamental skill/task that you need to practice?
Continuous learning, IMO. You can't be DROPE if you don't know what other people are doing. It's human nature to try and find a comfort zone and coast, but for programmers this is a downward spiral of lowering productivity. Once you start reinventing the wheel you are no longer productive and your reinventions are likely to be inferior to what has already been done.
Learning is hard work so one needs to keep that muscle in shape. So even if you don't have anything you need to learn now, you should still be doing it just to be ready for the time when you do need to - that is, practicing learning.
If you make an idiot-proof program, _you_ probably won't be able to use it.
That's an interesting postulate. If we rule out the typical cases of "lock yourself out of your home" by inattention, e. g. through forgetfulness, obfuscation or over-the-top security, that leaves this question: Would you be able to create a program that's more intelligent than you are? And as idiots are always the others, and you usually take this as your gauge, how probable is it? ;-)
I disagree with "Do It Yourself" - at least as it applies to the "real world". There's a distinct difference between "school work" and "paid work". In the first copying is cheating and in the second copying is productivity. I agree that a person learns the best by doing, but they don't often come up with the best result. You might fiddle around with something to learn the concepts, but you don't build your enterprise app that way.
The take away from the crypto post was that you should not try and roll your own. All non-trivial, real world, problems fall into this category. There are experts and a body of work out there (especially with the rise of Open Source) that far exceed anything a single dude with a computer can come up with.
At the end of the day, we, as programmers are (or should be) judged by how productive we are. Did you write a high quality program in a reasonable amount of time? Not how clever you were. It's been shown again and again that the best programmers are the humble ones that know their limitations and work within them.
Hey Now Jeff,
Omnibus - for all every. The page screen shot is classic still enjoying your blog.
One often forgotten lesson:
Code is twice as hard to read than it is to write, so you should only code at half smartness, or you won't be able to understand it when you come back to it later.
@Matt, re DROPE:
I've just been calling that DROP (same meaning, without the "Either"). It's part of the wheel reinvention problem that comes along quite a bit. When you're working for such a small company as I am, it's always important to remember that 10 minutes to search for and download something useful is a lot better than a week writing it yourself.
Just bought a copy from Amazon. I love your blog and if this book is as good as your site then I will be a happy man.
If not, then I still have your site to read every morning.
Kee Dewdney is great, I used to love his columns in Scientific American when I was a kid. If you can find his book "The Planiverse", it is also an enjoyable fantasy elaborating upon the famous Victorian excursion into lower dimensions, "Flatland".
Good puzzle here. Why is the door on the wrong side? Did Routemaster ever make a bus for a country where they drive on the wrong side? I doubt it.
I agree. This is a great little book. Every year I say I am going to work my way through the entire book. Then something else grabs my attention and I don't finish it. Now, you've gotten me to the point where, once I again, I say, "This time, I'm going to work my way through the entire book." We'll see.
By the way, your sample chapter is Chapter 49, not Chapter 33.
If your program has a bug remember that a good programmer is usually off by one somewhere.
Indeed an excellent book. It succeeds, as did Kee's Scientific American column, in being both deep and lucid - a rare combination. This is accessible to the non-specialist who's willing to make the effort because for the most part he picks areas that are profound but can be explained simply. Like the old "minutes to learn, years to master" ideal for games.
It's also noteworthy that this stuff hasn't dated - it's a bit like Paul Graham's explanation that the basics of Lisp hasn't changed much in 50 years because Lisp is based on mathematics, not technology.
Good job getting this excellent book some new exposure. If you don't know this stuff it's truly mind-expanding. (And if you do know it the reminders won't hurt...)
This is the kind of book I go through every few years, usually when I'm trying to learn what all the hubbub is about the hot new language. Usually the fundamentals don't require learning a GUI library, and it seems every language has at least one GUI library. I don't have a particular book, but I search the web for "programming contests".
I'm interested to watch a run materialize on this book now on Amazon
You asked, so I checked. Last night, the book's Amazon sales rank was around 66,000, this morning it's 709.
"But if aliens are not sending us messages, there is no way for Drake's search program to discover this since there is no stopping rule. The hypothesis is non-falsifiable. At best, the SETI program amounts to only half an experiment."
For shame. He should come to terms with the fact that the halting problem is unsolvable. Half an experiment cannot be done, but the other half need not remain undone. Let each turist halt when bored.
"In the end, Hungry Hollow is threatened by developers. How can it be saved by a native grave?"
By letting managers abuse managed code?
What would be the fundamentals that a good programmer might forget?
I know I forget things like algorithms (sorts, searches, data structures) although I don't know if those are really basics...
I'll give a shout-out for A.K. Dewdney any time! Him, Martin Gardner, and Douglas Hofstadter are three of the Popular Science authors I grew up on. A. K. Dewdney couldn't write a boring book if he tried. Glad to see a new generation will be discovering him.
#163 on amazon now... glad I could contribute to its success, thanks for the recommendation.
I'm interested to watch a run materialize on this book now on Amazon and Half.com. I got one off Half for $4.43 plus shipping.
Shannon, thanks for that link.
I also found this page about what A.K. is up to currently:
I am currently working on a book about Newport Forest, as well as a book on the ups downs of mathematical research. As a skeptic on the 9/11 terror attacks, I also contribute to one of the many investigative websites flourishing on the web these days: physics911.net/public
Holy smokes batman, shakin' #1!
Matt - you should know how to do anything well enough to recognize whether another implementation is better or worse than you could do, probably, but I agree that beyond that it depends entirely on the maturity of your market. I know Jeff likes to work on cutting edge topics, where Do It Yourself may be the only reasonable option. ;)
On the other hand, mental exercises aren't any more pointless than mental games, regardless of how they apply to your work. There's a whole spectrum of things you can do to interact with people, ranging from open-source work to founding a company, but you exercise different parts of your brain by learning and applying the mathematical side of CS. Not to mention that insight into the complex algorithms we use helps us to better understand when to use and when to avoid them, what problems they can and can't solve.
A little rant about the usability of amazon for dutch users.
Click on the reccommendation/ amazon link.
I get a page from amazon.com.
Great, the book is available ($20).
Click on add to whishlist,login, and notice that is not my normal wishlist.
Go to amazon.nl, get redirected to amazon.co.uk , type in the title and find the book (20).
click add to whishlist, AHA , that's my normal wishlist!
Go to google, type "20 in euro" and find out it would cost me 29 euro.
I have an account there so amazon knows i live in nl and want my prices in euro.
Big Free supersaving/mailing, Hell yea!,Oh? I'm not eligable because i live in nl,and postal costs are allso high from uk to nl.
[For the geograpically challenged I probably live like 100km away from th UK,and 20km from germany.]
Ahh forget it, forget amazon.de(germany) too,I'll just go to bol.com, EUR 27,99,10% discount deliverd within 1 week (but most probably within 2 days).
And Actually was worse than that:
A few hours ago it was something like 19 + an obsecure 8 fee on amazon.co.uk.
A summary from my previous post.
A blogger i do respect and like to read uses an affiliate link to amazon.com.
Even if i ordered from amazon, the affiliate link is lost when changing to amazon.co.uk.
After that there are so many dumb UI and company bugs that i decide to forget about amazon.
*me: i get annoyed.
*Jeff:He lozes an affiliate link
*amazon: They deserve it.
Funny, I wondered if this blog would spike the sails... I actually ordered my copy yesterday. I look forward to reading more, this is a great blog and I always welcome the suggestions.
I wondered if this blog would spike the sails
Duh... I meant to say "sales"... time for coffee!
This is a beautiful book - I'd forgotten that I've got a copy until this post. Absolutely one of the best. Unmatched, and alongside Programming Pearls just fantastic.
I was a little surprised for you to describe it as "little" because it isn't that little - about 300 pages. But then I realized that now we have these damn tedious Wrox doorstops and boatanchors that take over 1000 pages to regugitate the man pages (or worse than that, an ambiguous and confusing plain lanugage walkthrough of the source code) but explain nothing.
We've lost a lot - the 70's and 80's had lots of great books - now we have very little.
So how much did you make off your affiliate link?
The analogy to how "A good musician might still practice arpeggios" doesn't quite fit. Performers need to keep up finger strength and dexterity, so they must (not might) do technical exercises. This is akin to professional athletes working out regularly.
I CAN WAIT TO JOIN. SO PLEASE SHOW/TELL ME HOW TO JOIN. REPLY TO ME VIA E-MAIL:email@example.com. Thanks!!!!
The new Turing Omnibus opens your eyes to new worlds. Everything from genetic algorithms, to pushdown automata, to computer vision techniques are fair game. This book doesn’t go into enough depth in any topic to actually teach you how to do anything - but it will teach what is possible, and will help you recognize the best tool for the job. You won’t understand the details of simulated annealing or the simplex algorithm, but when you encounter a new problem you will know the right approach to take, and will having a jumping off point for your research.
How can you not also mention "The Armchair Universe"? :-) (Same Author, earlier book.) I remember writing a QBasic program to draw the mandlebrot set based on the descriptions of the mathematics in that book!) It is a collection of his "Mathematical Recreations" columns that were published in Scientific American. While I've not read "The New Turing Omnibus," I do recommend the Armchair Universe. (What geek can't find the description of "corewar" interesting? :-)
List of books by this Author: