This book evolved over the past ten years from a set of lecture notes developed by the authors while teaching the undergraduate Algorithms course at Berkeley and U.C. San Diego.
The topics were carefully selected and clustered. No attempt was made to be encyclopedic, and this left more spaces to include topics traditionally de-emphasized or omitted from most Algorithms books.
This book consists of four parts:
Part I starts with the historical beginning,
RSA cryptosystem,
divide-and-conquer algorithms for integer multiplication,
sorting and
median finding, as well as the
fast Fourier transform.
Part II, the most traditional section of the book, concentrates on
data structures and
graphs; the contrast here is between the intricate structure of the underlying problems and the short and crisp pieces of pseudocode that solve them.
Part III deals with the "sledgehammers" of the trade, techniques that are powerful and general:
dynamic programming (a novel approach helps clarify this traditional stumbling block for students) and
linear programming (a clean and intuitive treatment of the simplex algorithm, duality, and reductions to the basic problem).
The final Part IV is about ways of dealing with hard problems:
NP-completeness, various
heuristics, as well as
quantum algorithms, perhaps the most advanced and modern topic. As it happens, this book ends the story exactly where it started it, with Shor's quantum algorithm for factoring.
Intended Audience :Instead of dwelling on formal proofs, this book distills in each case the crisp mathematical idea that makes the algorithm work. In other words, this book emphasizes rigor over formalism. Undergraduate students in Computer Science should be much more receptive to mathematical rigor of this form.
Author(s) : S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, University of California, San Diego
Publication Date : 22 May 2006
View/Download Algorithms
