 |
GetTextbooks.com
Compare Prices & Save up to 90% |
|
|
|
| Login | Sign up | My Wish List |
 | | Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani ISBN-10: 9780073523408 ISBN-10: 0-07-352340-2 ISBN-13: 9780073523408 ISBN-13: 978-0-07-352340-8 Paperback 2006-09-13 McGraw-Hill Science/Engineering/Math Find Lowest Price |
Editorials | ||
Product Description This text, extensively class-tested over a decade at UC Berkeley and UC San Diego, explains the fundamentals of algorithms in a story line that makes the material enjoyable and easy to digest. Emphasis is placed on understanding the crisp mathematical idea behind each algorithm, in a manner that is intuitive and rigorous without being unduly formal. Features include: The use of boxes to strengthen the narrative: pieces that provide historical context, descriptions of how the algorithms are used in practice, and excursions for the mathematically sophisticated. Carefully chosen advanced topics that can be skipped in a standard one-semester course, but can be covered in an advanced algorithms course or in a more leisurely two-semester sequence. An accessible treatment of linear programming introduces students to one of the greatest achievements in algorithms. An optional chapter on the quantum algorithm for factoring provides a unique peephole into this exciting topic. In addition to the text, DasGupta also offers a Solutions Manual, which is available on the Online Learning Center. "Algorithms is an outstanding undergraduate text, equally informed by the historical roots and contemporary applications of its subject. Like a captivating novel, it is a joy to read." Tim Roughgarden Stanford University | ||
Reviews | ||
A Supplemental Text The top choice for an algorithms text is generally considered to be Cormen, et al. However, Cormen is not unassailable, and an author that is able to provide an alternate and useful approach into the subject can find his audience. Skiena's Algorithm Design Manual comes to mind in this regard, and some even consider it superior to Cormen. Dasgupta, Papadimitriou and Vazirani "Algorithms" provide yet a third approach. While less comprehensive than either Cormen or Skiena, the tone is more conversational and relaxed. At only 320 pages, it cannot be expected to be comprehensive. Certain standard topics are barely covered (such as binary search trees and red black trees) if at all. Because of this, it can only be a used as an introductory text, or maybe used as a supplement to Cormen or Skiena And now for the bad... "Algorithms" does not have answers to any of the end of chapter problems. There really is no justification for this. Yes Cormen and Skiena also do not provide answers...but as I mentioned earlier, if they want to compete with Cormen and Skiena, they have to provide something new, and giving students the answers to some of the problems would have been the easist way to accomplish this. The authors exhibit enough inaccuracies when discussing non-computer science topics (ie, linear algebra, cryptography, and quantum mechanics) that at times, you have to wonder about their command of the main topic -- algorithms. So, consider, for example, when discussing the simplex algorithm on page 213, they incorrectly define what is meant by a hyperplane. The standard definition can be found in Hoffman and Kunze (i.e., in a vector space of dimension n, a subspace of dimension n-1 is a hyperspace or hyperplane). Their definition is simply wrong. Moving on to cryptography, they discuss the one time pad, the AES, and the RSA cryptosystems. They dismiss the one-time pad as a toy scheme, and suggest that at the other end of the spectrum is the AES scheme. The fact is just the opposite -- the one-time pad has been proven to be a completely secure and unbreakable cryptosystem, and the AES has not been proven so. Also, comparing the one time pad to the RSA, one should note the RSAs security relies on the non-proven difficulty of factoring large numbers...and if quantum computers ever became a reality, the fact is the RSA would be broken. The reason the one time pad is not used is not because it is a toy. It is not used because in the one-time pad, the symmetric key can only be used once, and so a new problem -- key distribution -- is introduced, which in fact makes the one time pad impractical for most applications. Moving on to algebra, on pg. 33 we see the statement "The mapping x|-> x^e mod N is a bijection on {0,1,2,...,N-1}". A mathematician would properly state this as onto, not on, {0,1,2,...,N-1}, since the map is a bijection. Finally, the last chapter is on quantum algorithms (big marks for bravery), which neither Cormen and Skiena do (Skiena has a new edition of his book on the way, so we will have to wait and see if his latest covers it). From a physics point of view, the chapter falls way short. They attempt to introduce qubits by discussing a single electron atom. The problem is they do not seem to realize you cannot use an atom for both a qubits and a classical bits discussion. An atom is 100% quantum mechanical. (By comparison, when Feynman discussed the double slit experiment, he used electrons to illustrate the quantum effects, and bullets for the classical case.) Therefore, the author's statement on page 298 "These are the two possible states of the electron in classical physics" is just nonsense. In classical physics, the electron does not have a first excited state, it has a continuum of possible states -granted, the states are not stable and the electron will promptly spiral into the nucleus, but that is a separate issue. The authors also give a quote by Feynman: "I think I can safely say that no one understands quantum physics". Yes, at the time Feynman said that, that was probably true. But quantum theory has not stood still, and Feynman perhaps did not know the theory of decoherence, or perhaps he considered it speculative. But, as decoherence has now been observed in the laboratory, there is in fact a school of thought, championed by Roland Omnes, which claims that quantum mechanics is now, with the addition of decoherence, finally in some sense understood. ...Also, they introduce a two particle system as a tensor product state. It is true this is the correct description, but it is not correct to do so without any motivation of why (why not a direct sum of vector spaces, for example? Why must it be a tensor product of vector spaces?) and without bothering to give a definition of a tensor product. I encourage the interested reader to consult "Quantum Mechanics - a modern development" by Ballentine and also the outstanding "The Quantum Mechanics Solver" by Basdeveant and Dalibard if they truly wish to understand the modern Quantum Theory topics which the authors have so poorly treated. Still, despite the above issues, as long as one is using this book as a supplement, and not the main text, I think it can serve as valuable resource for the algorithms student. | ||
My first choice as an instructor I occasionally teach algorithms at CU Boulder to our undergraduates. This book accomplishes what it set out to do: provide a comprehensible (but not comprehensive) treatment of a core piece of Computer Science at an affordable cost. That we get one of the greatest researchers in the area (Papadimitriou) alongside two other distinguished authors is just icing on the cake. The first printing had numerous errors, though the online version of the book had already corrected many of them. I haven't used the book since then, but will in the Fall, and I'd expect with the vigor already invested by the authors, the book will be in even better shape. I'm glad they wrote this thing.. it was long overdue. | ||
Author's student: By Far The Best Algorithms Book! As a CS undergrad at UC San Diego, the author used rough drafts of this book to teach the algorithms course I took as a student. Although we also used the Cormen("The Bible") Algorithms book for casual reference, this text is by far better to explain the concepts behind the algorithms. I must say that the author presents the course with this text far clearer and superior than the usual dry mathematicians and the contents of the material reflects his expertise in lecturing and writing. The lucid writing makes it a joy to actually read an algorithms book, and the exercises are definitely worth investigating. This book simply makes algorithms fun! | ||
Complex Computing Algorithms just made story-like Algorithms is a complex topic in computing that needs tentative learning. The authors of this book really succeeded in making learning algorithms more enjoying, interesting, and easy yet comprehensive and advanced. This is a difficult equation, but this book really achieves it. It takes you from the early foundation with the Fibonacci algorithm till the complex graph algorithms while explaining each milestone all over the way. The was they present this subject is in a story manner or a casual discussion between two computing professionals which makes the book interactive, easy to access, and comprehensive. I recommend this book for both beginner and advanced readers in the field of computing. | ||
Very well written and quite clear I took the class with one of the authors, professor Dasupta. This book explains all the algorithms in a very clear way. Can't go wrong with it! | ||