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
Data Structures and Algorithms in Java by Adam Drozdek (2001, Book, Illustrated) | US $14.95 End Date: Thursday May-24-2012 11:44:31 PDT Buy It Now for only: US $14.95 Buy it now | Add to watch list |
I purchased this book for a college course. It came in plenty of time for school.
I will always buy school books first from amazon. I will not pay full price for a
book that is almost in perfect condition. Amazon is a great way to buy books.
Amazon User Rating: 5 / 5
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!
Amazon User Rating: 5 / 5
I took this class as a student and I was not impressed at all by the text. The text is far too informal. The problems unchallenging. The algorithms uninteresting. The historical content was far too sparse. If you are going to have history, have enough that it satisfies or have none at all. I would recommend “How to Think About Algorithms” by Jeff Edmonds over this book any day.
Amazon User Rating: 2 / 5
I took a course that utilized this book a year ago, and I was very impressed with the quality of both the text and the exercises. With few exceptions, the text explains the concepts very accurately and understandably. The exercises are at the right level: they are difficult but solvable problems, and, most importantly, they reinforce the material extremely well.
I’d strongly recommend this book to anyone looking for an introduction to algorithms.
Amazon User Rating: 5 / 5
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.
————————————–
Update to review: Posted May 27, 2009 |
————————————–
My criticism of the authors incorrect classification of the one-time pad as a toy scheme has (there was in fact never any doubt) been fully verified recently in China, which has just completed the world’s first quantum cryptography network, making successful use of the one-time pad. The experiment demonstrated real-time voice telephone communication using the one-time pad…and work is in progress to try to extend the result to video conferencing. The Chinese team states they will fall back on the classical AES if necessary, but only if the key generation rate is too slow. However, the one-time pad is clearly first choice – hardly a toy.
(FYI: The Chinese team’s paper, “Field test of a practical secure communication network with decoy-state quantum cryptography”, is at the time of this writing, free and available here:
http://www.opticsinfobase.org/DirectPDFAccess/8442BF5D-BDB9-137E-C05FD385BDEF0463_178975.pdf?da=1&id=178975&seq=0&CFID=39796393&CFTOKEN=68109129
It is clear that when the Algorithm’s authors foray into fields outside their expertise of algorithms and into mathematics, cryptography, and physics the level of scholarship they display is significantly lower than what one might expect at a world class institution such as is Berkeley. Much of the reason for this is of course the difficulty of the non-algorithm subjects. But part is also due to a cavalier and sometimes sloppy approach that is encouraged by the informal tone of the text. It is for this reason, and the others previously stated, this text is currently unusable as the main text. However, it can be a source of supplemental examples, which is often a boon to the student.
Amazon User Rating: 3 / 5