Archive for the ‘Algorithms’ Category

The Elements of Computing Systems: Building a Modern Computer From First Principles

August 1, 2007

51jfxm2x1yl_aa240_.jpg

I already wrote a review of this wonderful book, written by Noam Nisan and Shimon Schocken, at Amazon.com, so I’ll just repeat it here:

I highly recommend this book if you are interested in learning about computer science. The book is organized around the idea of building a computer from the fundamental logic gates up–starting with the hardware (combinational logic gates, arithmetic logic units, sequential logic gates, the CPU and memory) and then through the software hierarchy (starting with the machine language, and working up through the assembler, a virtual machine, a compiler for a high-level language, and an operating system). As a “by-product,” one learns, by very relevant examples, many fundamental concepts of computer science.

You can just read the book, but the best idea is to follow the authors’ advice and do the projects where you implement every necessary piece of the computer system yourself. The projects are all very well organized. All the software modules necessary to emulate any part of the computer, plus half the chapters from the book, are available for free download from the authors’ web-site. It all works beautifully. If you want to skip any of the projects, you can, because the software is organized in such a way that it will use built-in modules instead of the ones you built if necessary.

The authors seem to have extensively tested the whole approach through the courses they have taught using this material. I also noticed that Harvard’s Computer Science 101 course is being taught based on this book. I have been using the book for self-study with absolutely no problems–in fact I have never had such a great experience with a self-study course. All you need is a Windows, Linux, or Mac OS X computer and access to the internet, and you can give yourself a wonderful education in computer science.

In terms of prerequisites, you only really need to have some experience with programming (e.g. with C, or ideally with Java or Python). I think that the book should work well for students or hobbyists who don’t have any more experience than that, but it is also great for much more experienced students, as a kind of integrative summary of the field. I also think the book is perfect for graduate students or researchers from other fields who want to learn how digital hardware and software systems are actually engineered.

Finally, I just want to compliment the authors on the extraordinary care that they have taken with the whole project. The computer design that you build up is wonderfully elegant–at every stage the design is just as simple as it can be while being sufficient. Every piece of emulation software works as advertised. Even the extra powerpoint or .pdf tutorials are nicely done. This is really quality work, and using it is just a real pleasure. Finally, the source code for all the software provided by the authors is available, so if you wanted to extend the provided emulators, you could do that.

In summary, I give this book my unqualified highest recommendation.

David MacKay’s “Information Theory, Inference, and Learning Algorithms”

August 1, 2007

sept2003cover25.gif

This is an easy book for me to recommend. David J.C. MacKay is a professor in the physics department of Cambridge University, and he is a polymath who has made important contributions in a wide variety of fields. This textbook is an excellent introduction to modern error-correcting codes, compression, statistical physics, and neural networks. It is tied together by a recurring appeal to the power of Bayesian methods.

David wrote this book over the course of many years, publishing his drafts on the web. You can still view the entire book on the web here. But the book is very inexpensive; unless you’re very poor, you’ll really want to buy a copy.

As Bob McEliece (a professor at Caltech and Shannon medalist) wrote, “you’ll want two copies of this astonishing book, one for the office and one for the fireside at home.” I know this is true because I actually have two copies; I bought my own copy as soon as the book was published, and then found that David had kindly sent me a copy.