Book Review: M. Garey, D. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness

Today I'll review the wonderful Computers and Intractability: A Guide to the Theory of NP-Completeness. I first heard about this book while watching Steven Skiena's online video lectures (which I blogged about recently) three or four years ago, where he recommends it as the best book on the topic (and actually uses it in class). I've since read it several times and used it as reference many more, and before going into the details, I'll just say I think it's awesome.

And now for the details :). This is not your standard "read before sleep" book. It's more like a math book (and math books are read with pen and paper in hand :). When I first tried reading it (that was when I had just a basic grasp on the topic), I found it pretty hard going, and had to restart a few times. This is not to say it's not well written; on the contrary, the writing is great. It just took me a while to get into the right mindset for it. If you're a fan of formalisms and Turing machines, you'll have no problems whatsoever. If you're not, but still want to understand this stuff, you'll have to make more of an effort, but I think it's well worth it. The book doesn't force formalisms down your throat for no reason, but develops the theory from the formal to the informal and more intuitive (but still correct) in a very elegant way.

The book is logically divided into three parts. In the first part, you'll learn why complexity matters and some basic terminology regarding Turing machines, languages, encoding schemes, decision problems and "real problems" (and how they all relate to each other) and the all important polynomial transformation between problems. Then you'll read about what it means for a problem to be in P and NP. After this introduction, the authors present Cook's theorem that is basically the origin of the whole story, in which the famous satisfiability problem is defined and proved to be NP-complete. What follows are proofs (via polynomial transformation) that "6 basic" NP-complete problems are indeed NP-complete. These are 3-satisfiability, 3-dimension matching, vertex cover, clique, hamiltonian circuit and partition. These transformations are a bit more involved then most (since you don't have many problems to choose from when you start building up the NP-complete set), as is the proof of Cook's theorem, but I find them mathematically beautiful (and in general, constructing NP-completeness proofs is a nice mind "game", not to mention useful in many cases :). However, on your first reading, you'll probably want to skim these and just get the intuition behind them and understand "the big picture".

After that, the authors take a step back and try to define three general techniques for constructing NP-completeness proofs (restriction, local replacement and component design) and show a few examples of each. You are then presented with fourteen exercise problems on which to try the techniques out. This ends the first part of the book (about 65 pages).

The second part of the book starts with exploring how the NP-completeness of a problem changes when you constrain it or change it. Then it explains what it means for a problem to be NP-complete in the strong sense and what are Turing reducibility and NP-hardness. The next chapter gives some basic information about dealing with NP-complete problems through approximation algorithms, but what I think is far more interesting (in the context of this book), they show how using the theory of NP-completeness you can prove that some problems can't even be approximated well (for certain definitions of "a good approximation" which I won't go into here) in polynomial time (unless P = NP). The second part ends with expanding the complexity hierarchy with some more advanced concepts like co-NP, gama-reductions and gama-completeness, #P-completeness, PSPACE, DLOGSPACE, EXPTIME etc. (these are all covered with examples and provide solid intuition about what these things are on the first reading, but need to be studied a bit more carefully for full understanding).

Finally, the third part of the book is a catalog of about 300 NP-complete problems (sorted into several categories). This is a great reference! If you have an NP-complete problem on your hands, chances are it has a name and it's on this list :) Given the age of this book, I'd imagine the current list of known NP-complete problems is somewhat bigger, but this one is comprehensive enough that you can probably at least find a problem that is close enough to your problem that you'll be able to construct a proof yourself.

So to summarize, this is an awesome book. NP-complete problems pop up just about everywhere, and it's important to be able to recognize them (and not waste too much time trying to solve them to optimality quickly). My advice for a reading algorithm: read the first part, skimming over the proofs for intuition, then reread it a month later going through the proofs with pen and paper. Then read the second part (it's not as important so you can skim it or read it for full comprehension, depending on how much you want to get out of it) and skim the catalog to get a feel for which problems are there (so you can use it as a reference). You'll recognize quite a few of them, probably some you've met at work :). Also, even if you're not in Computer Science, you might like this book from an epistemological perspective ;)

Book Review: Matt Weisfeld: The Object-Oriented Thought Process

Today I'll write a quick review of the ambitiously titled The Object-Oriented Thought Process (3rd Edition) (Developer's Library).

Just by browsing through the table of contents (which is always a nice way to start thinking about buying or reading a book), you'll see that this book attempts to cover a lot of ground. In fact, on the second edition cover, the subtitle said "An introduction to object-oriented concepts for programmers looking to master modern application development tools, including Java and .NET" (my emphasis), but thankfully, they decided to remove that :). In reality, this book scratches the very surface of a lot of facets of "modern application development", but lacks any depth that could lead you to mastering anything. What you get is basically a lesson in object-oriented terminology. You'll hear about classes, objects, encapsulation, inheritance, composition and all the usual suspects, and then see a few (standard and very artificial) examples modeled with CRC cards and UML.

Unfortunately, the book then gets sidetracked into relational databases, XML, HTML, CSS, JavaScript, JavaBeans, CORBA and Web Services (you get about two to three pages about each). Finally, there's a twenty page chapter on design patterns that tells you what they are and lists a few. You can skip this whole part.

To it's credit, the book is short, well written and (for the most part) correct. If you've just heard of object-oriented programming this book will give you a nice overview of what it's about, and possibly keep you from forming some misconceptions. On the other hand, if you're already familiar with OOP, you won't really benefit much. I also think this might be a good book for people who aren't really planing on being developers but will be talking to developers in their work (like managers and marketers) as it is lightweight enough and doesn't really require previous knowledge (there's some Java and C# code in there, but it's very basic and not very important either). Finally, since this book doesn't hold any value as a reference and reading it more then once doesn't make much sense, if you want to read it, I recommend you lend it at the library and save some money. :)

Book Review: M. Feathers: Working Effectively With Legacy Code

First off all, happy Easter!

For my first book review, I decided to write about a wonderful book I discovered about a year ago that I think not too many people know about, and that is Working Effectively with Legacy Code (Robert C. Martin Series).

I got this book in my first week as a Google intern. Since I had some spare time in the evenings and on the weekends I read it right away and found it absolutely amazing. It basically talks about how to deal with the fact of changing requirements. In the early days of OOP, there was a tendency to over-engineer a project (trying to predict every possible change ahead of time, overuse of inheritance etc.). People soon realized that, while proper design is essential, you just can't predict every possible change, and sometimes you'll have to change your design to accommodate the new requirements. This is where the idea of refactoring code comes in. It's a process in which you change your code while preserving behavior, making it "nicer", in an attempt to make the behavior easier to change in a later step.

The main problem here is preserving behavior while changing things. This can lead to all sorts of headaches and problems, but can be made a lot easier if your code has tests. This is also the main premise of this book; the author loosely defines legacy code as code without tests (and also code that's older then three months or so, which is probably a lot shorter than most people would think). There has been some controversy over tests a few months ago in the "blogosphere", mainly in posts and podcasts by Joel Spolsky and Jeff Attwod on one side, and Robert Martin on the other, all of whom are well respected (for good reason) in the community. Basically, Joel and Jeff argue that Test Driven Development is going too far, and test can make your code harder to change (because you have to change your tests as well). While this might be true sometimes, I don't think it's a valid point if you design your test right. You should be testing your APIs and not your implementations (which is certainly not always possible, but should be a goal). Sure, writing a piece of code (a class for example) will take a bit longer initially because you'll need to write tests for it, but you get several benefits from that. First, you write code that uses your class, therefore exposing some possible weak spots in your API. Second, once you're done, you can be reasonably sure that your class does what you want. Also, when it comes time to change the implementation (or the API, which is not too big a deal if it's a small internal API - and someone else might be making the change, or it's been a year since you wrote the initial code), you'll have a safety-net since you'll be able to tell early if you broke something (there might of course be things you miss, but a lot fewer of them). On the other hand, you just can't unit test everything, but that's OK too. You can do some tests manually, or use specialized tools to automate that as much as possible. I feel that unit tests also provide great documentation for what the API is doing and how to use it (still, you should write more formal docs for external APIs :).

One area especially where I think unit tests are extremely important are scripting languages. Many people used to think (or still do) that programs in scripting tend to be harder to change or more prone to "silly" bugs due to typos that don't get detected by the compiler. While this can be somewhat mitigated with using good IDE-s, having solid unit tests will pretty much eliminate these kinds of bugs and you'll be dealing with much the same bugs you were dealing with in compiled languages.

So back to the book... This book will show you a wealth of options for creating this testing safety-net where there isn't any through a series of realistic examples in Java, C++ and C (although most of the techniques presented are applicable to most languages). It starts of by talking about breaking dependencies as the crucial step in getting (parts of) legacy code under tests. BTW, there is a lot of great material on dependency (and dependency injection) and how testing can make your code less coupled in the first place on the Google Testing Blog. Well worth reading and watching the YouTube videos.

Then it introduces fakes and mocks that let you replace complex objects and interactions in your tests with simple ones, thus making tests faster (connecting to a fake database locally, vs. connecting to a database over the network for example), more focused and less flaky (they won't fail if the network fails or the database dies). Then Feathers talks about seams, which are ways to change behavior of some code without editing in that place. He introduces a lot of techniques that range from fairly obscure (like preprocessing and linking seams) to the more common object seams.

In the next third of the book, he discusses how to deal with things like big classes that do a ton of things, how to go about understanding how objects interact in a complicated system and things like that. This part is mostly about creating the right mindset for dealing with legacy code, although most of the techniques presented are quite practical.

Finally, the third part of the book contains the dependency breaking techniques the first two parts have been building up to in a really nice catalog that can be a great reference. You should read this book once from cover to cover to get it, and then skim it a few times in the following year to index the techniques better into your brain (and of course use the book as a reference).

In conclusion, I think this book is definitely worth reading (if not owning). Even if you don't deal with legacy code on a day to day basis (which is probably rare), it will change the way you look at the new code you're writing, and hopefully convince you that you should be writing unit tests. Try it! :) (if you can get someone to review your code as well, you'll sleep even better, but that's another topic :).