Algorithm Design by Jon Kleinberg, Eva Tardos, Iva Tardos

Algorithm Designby Anonymous

Reader Rating:
See Detailed Ratings

July 30, 2005: The text offers an interesting blend of rigour and informality. The numerous proofs in each chapter have that rigour. Yet what may be more important is how the text remains accessible to a primarily undergraduate audience. The book is not just a compendium of common algorithms in computer science, and proofs about them. The authors place a stronger emphasis on motivating how to develop an intuitive understanding of the problems that the algorithms address, and of how to shape new algorithms. Or, possibly, apply or modify existing algorithms to new problems. If you compare the text to Knuth's classic 'Art of Computer Programming', then you might find Kleinberg and Tardos more accessible. (At least for undergraduate readership.) Also, the extensive exercises at the end of each chapter often have contexts germane to the Web. For example, the links in web pages are used to motivate problems in graph theory, where we have directed (unidirectional) graphs, due to the one way nature of links. More generally, the recent, contextual nature of the problems may appeal to some students. Knuth had many exercises listed in his books, but they can be too abstract for most students. The text also has a very interesting chapter on NP problems. The authors address a very practical situation. Even if you find that you have a problem that is NP complete, it is not necessarily the end of the story. For real life reasons, you may have to find an approximate solution that is computationally feasible to evaluate. The chapter offers suggestions and examples that may be of help. (More formal texts might merely stop at proving NP completeness.)