Customer Reviews

Algorithms from P to NP, Vol. I: Design and Efficiency

5 star:		(2)
4 star:		(1)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

I was required to purchase a leather-bound copy of this text for a Junior (undergraduate 3rd year) course. It is a wonderful book and I came across the Amazon listing just now on a search for volume 2.

This text is wonderful because it contains information relevant to students of Computation at all levels from Undergraduate onward. Fundamentally, the book is about analyzing the "complexity" of algorithms -- which is a way of defining how long some operations will require to complete. This volume concentrates almost entirely on algorithms which can be solved in an amount of time that is a polynomial function of the number of inputs.

Even formerly mundane-seeming algorithms as sorting are made more exciting by the inclusion of advanced material, for example on sorting networks. The book also includes very exciting algorithms involving two-dimensional (2D) geometric searches and other operations such as merging polygons. Graph theory is covered in particularly special detail with this text. Seven greedy algorithms are classified according to multiple taxonomies according to different mathematical views. Generalized pattern matching (such as regular expressions, finite state automata and beyond) is covered from beginning to advanced detail, as well.

A key quality of this book, I think, is that each reader will make "so much" of each section -- and then the reader might move on the next topic, and read up until the point of covering those parts of the book which seem readable. It might be good to read about twice during college and periodically every 4-7 years thereafter, until you can read the whole book. I see parts I still have not read. The book is written in a combination of clear exposition but the each chapter's topic coverage ranges (smoothly) from the introductory to the very advanced. Most chapters end in "optional" sections as a hint that they are to be skipped by those early in their studies.

In contrast to other reviewers here at Amazon, I find the coverage of P vs NP and NP-completeness to be rather brief although very understandable. In my copy of the text, there is a discussion on page 60 of NP-completeness, and that is the only such exposition mentioned in the index. I see that my copy of Volume I bears a "P" on the cover and on page 60 the text indicates that more detailed coverage of "NP" algorithmic complexity will follow in the second volume.

This is a very good book, well written with a lot of material -- BUT NOT FOR A UNDERGRADUATE student. Undergrads looking to get some basic help and introduction to NP Completeness, should avoid this book .. But others with a strong mathematical background and most importantly a lot of interest in this very interesting theory should definitely invest.

Hope this helps..

Even though it is more than ten years old now, Moret & Shapiro is still the best book available on NP completeness and related topics. In a way I disagree with other reveiwers who advise that only graduate students read this book. It all depends. I have known a number of graduate students who might not have understood this material as well as some undergraduate students. It is not so much a matter of college level as it is your personal tools for dealing with abstraction and complexity.