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: Andrew Tanenbaum: Computer Networks (4th edition)

Today I'm going to review the classic Computer Networks (4th Edition) by Andrew Tanenbaum.

I first read a significant portion of this book a few years ago when I took a class in computer networks at the University (it's a 4th year graduate course, considered by most to be one of the hardest in the program) that was mostly based on it. Since I'm a big fan of reading books cover to cover (which is BTW the ideal way to read this particular book), I took some time the last few weeks and did just that. Having read most of it before, and dealing with networks quite a lot in my work and spare time, I read it mostly for review value.

As the title suggests, this is a very general book, and as such holds real value. After all, in today's world, who can ignore networking? If anything, networks will become more and more important, and understanding them is already pretty much mandatory for anyone in ICT. This book will give you a great framework for dealing with all sorts of networks you might come across in the wild. For the most part, it explains how networks are built in layers, with each layer offering services to the layer above it and consuming the services of the layer below it. Two major reference models are covered: the OSI/ISO one and the TCP/IP one. You will get a solid understanding of just how much politics influences standard's bodies and better understand why some things are not as good as they could be :).

For the most part, the book then goes through the layers (of something that I've heard called the "Tanenbaum hybrid model" which is basically what is used in practice (in the Internet for example). You will learn some basic things about the physical layer like the kinds of cables in use and their characteristics, fiber, radio, microwave and satellite transmission..., encoding bits with volts. After the physical layer, there's a high level explanation of how the telephone system works. Then he goes on a detailed tour of the data link layer (which is basically a direct "wire-like" connection between two machines), talking about error correction codes (Hamming code, CRC), framing and flow control. Here he also discusses Bluetooth, Ethernet (in some detail), WLAN etc. In covering the network layer, the main focus is on routing, congestion control and internetworking. There's also a relatively detailed discussion of the network layer in the Internet where IPv4 and IPv6 are discussed (among other things). Then he goes on to cover the transport layer which mainly deals with establishing connections, retransmissions and congestion control. Here he talks a bit about UDP and TCP, which are the "main" transport layer protocols in the Internet. Finally, there's a chapter about the application layer that features pretty much anything you've heard about, from DNS and e-mail to the World Wide Web and its protocols, to multimedia.

The book finishes with about 200 pages on network security, which covers your basic cryptography and different protocols in the different layers that implement various measures. There is also a great section on further reading per topic.

One final note. Although this is the 4th edition of the book, the book was released in 2002. which is (in computer terms) ancient. To put things in perspective, Wikipedia was started in 2001., YouTube in 2005., social networks didn't really exists in 2002. etc. Still, the things covered in this book have not changed that much so this should not worry you too much.

So to summarize, this is an awesome book that I think everyone in ICT should read. It's OK as a reference, although you'll probably want to consult specialized literature for specific topics (like the relevant RFCs for Internet related stuff). It's pretty expensive, so you might want to get a used copy, but it's worth owning!

Using vector and deque "the right way"

If you're using the STL, chances are you're using vector and deque a lot. They are two of the three sequences defined in section 21.1.1 of the C++ standard (the third one being list which I won't talk about in this post).

The nice thing about dealing with these sequences is that they manage their memory automatically when you're using push_back and pop_back and you don't really have to think about it. Naturally, I did a search to see if this has been beaten dead, and sure enough, I found a great article about it by Andrew Koenig and Barbara Moo of Accelerated C++: Practical Programming by Example (C++ In-Depth Series) fame (also see Koenig lookup).

Instead of repeating everything that's in there, I'll just recap the main point. The C++ standard (in section 23.2.4.1) guarantees amortized constant time insert and erase at the end for vector. This basically means that you can grow a vector from empty to size O(n) in O(n) time using push_back, although some individual push_back calls might take linear time (the ones that cause reallocation, which consists of allocating a new block of memory, copying the old objects, destroying them and deallocating the old memory block). One subtle thing to note here is that reallocation (which should mostly be transparent and not something you worry about) invalidates pointers and iterators into the sequence.

The vector class offers some facilities that let you take a more active role in this memory management process. These first function is void reserve(size_type n) which makes the vector allocate enough memory for at least n items, effectively making all push_back calls up to n items take constant time. The other function is size_type capacity() const that lets you know the currently allocated memory for the vector.

The standard doesn't define how this is to be implemented, but by reading around and looking and source code, it seems most implementations grow the vector exponentially, with factor between 1.5 and 2 (although there might be others). Fortunately, even if you can't access the source of your implementation, you can easily test it out with a program like this:

#include <cstdio>
#include <vector>

int main() {
    std::vector<int> v;

    std::vector<int>::size_type old_capacity = v.capacity();
    for (int i=0; i<1000; ++i) {
        v.push_back(i);
        const std::vector<int>::size_type new_capacity = v.capacity();
        if (old_capacity != new_capacity) {
            std::printf("%4u %4u\n", (unsigned)v.size(), (unsigned)v.capacity());
            old_capacity = new_capacity;
        }
    }
    std::puts("growth done");
    for (int i=0; i<1000; ++i) {
        v.pop_back();
        const std::vector<int>::size_type new_capacity = v.capacity();
        if (old_capacity != new_capacity) {
            std::printf("%4u %4u\n", (unsigned)v.size(), (unsigned)v.capacity());
            old_capacity = new_capacity;
        }
    }
    std::puts("shrink done");

    return 0;
}

On my machine, this outputs

   1    1
   2    2
   3    4
   5    8
   9   16
  17   32
  33   64
  65  128
 129  256
 257  512
 513 1024
growth done
shrink done

As you can see, the factor here is obviously two. Two other points are of interest. First, the vector starts out with no allocated memory. Secondly, the memory is not released when the size shrinks. This means that the memory will be allocated until the object is destroyed, unless you explicitly call clear or resize. Also, if you use reserve with some amount just before the loop, you'll basically seed the sequence with something other then one. The point here is that you get a lot of small reallocations at the start, which does seem like a waste.

The standard actually recommends using vector "by default" (section 23.1.1.2). Browsing around Herb Sutter's Guru of the Week I stumbled upon an entry where he recommends using deque as the default. So, for a bit of background, a deque is a sequence that supports constant time insert and erase operations on both the front and the end (via push/pop front/back). It also supports random access iterators and random access via operator[] and at(), but random access is not constant time since a deque is basically a linked list of fixed size memory chunks. This works quite well for memory management as the memory chunks are small and no reallocations are required when the sequence needs to grow. Still, the point Herb is making is kind of defeated by the timing data he includes in the post since vector outperforms deque in pretty much everything (I'd say, as expected). Still, deque is a great sequence and is actually used by both stack and queue by default (for good reason) and is a great structure for implementing 0-1 BFS.

Going back to vector, I'm wondering how people use reserve in "real life". Often, I'll have a pretty good idea of how big a vector will end up after a loop, and using reserve in those cases seems like the right thing to do.

std::vector<int> v;
v.reserve(n);
for (int i=0; i<n; ++i) {
  v.push_back(i);
}

Should be better then

std::vector<int> v(n);
for (int i=0; i<n; ++i) {
  v[i] = i;
}

because the latter actually initializes n ints to zero in the constructor (and the benefit would increase when the items in the vector are objects with more state and possibly elaborate default constructors).

Now the strange bit. Even though I've been programming in C++ for about five years now and I feel I know it really well and consider it my "main language", I've never used it on a multi-person project. In fact, I've never done a project over a few thousand lines in it, although doing a quick grep on the code I have on my home machine shows about 95k lines of C++ code I wrote. Due to strange circumstance, I've only had a chance to work on smallish sized projects (~5k lines) in C#, JavaScript, Python, PHP and Java, and on a medium (~30k lines) project in Java. So, I'm asking you, C++ developers, what are your experiences with using vector and deque in real projects? Is reserve used and how do you estimate the right size to use? Thanks!

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 :).