Algorithms

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.

From the webpage:

This is a penultimate draft of our soon to appear textbook.

For more information, visit http://www.mhhe.com/dasgupta.



Table of contents

Preface

Chapter 0: Prologue

Chapter 1: Algorithms with numbers

Chapter 2: Divide-and-conquer algorithms

Chapter 3: Decompositions of graphs

Chapter 4: Paths in graphs

Chapter 5: Greedy algorithms

Chapter 6: Dynamic programming

Chapter 7: Linear programming

Chapter 8: NP-complete problems

Chapter 9: Coping with NP-completeness

Chapter 10: Quantum algorithms

Entire book (draft)

The published version was reviewed by Dean Kelley (Dean Kelley. 2009. Joint review of algorithms by Richard Johnsonbaugh and Marcus Schaefer (Pearson/Prentice-Hall, 004) and algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani (McGraw-Hill, 008). SIGACT News 40, 2 (June 2009), 23-25. DOI=10.1145/1556154.1556159 http://doi.acm.org/10.1145/1556154.1556159)

Who noted:

….Eschewing a formal and traditional presentation, the authors focus on distilling the core of a problem and/or the fundamental idea that makes an algorithm work. Defi nitions, theorems and proofs are present, of course, but less visibly so and are less formally presented than in the other text reviewed here.

The result is a book which fi nds a rigorous, but nicely direct path through standard subjects such as divide-and-conquer, graph algorithms, greedy algorithms, dynamic programming, and NP-completeness. You won’t necessarily find every topic that you might want in all of these subjects, but the book doesn’t claim to be encyclopedic and the authors’ presentation doesn’t su ffer as a result of their choice of specifi c topics.

Nice collections of chapter problems provide opportunities to formalize parts of the presentation and explore additional topics. The text contains plenty of “asides” (digressions, illuminations, addenda, perspectives, etc.) presented as boxes on some of the pages. These little side trips are fun to read, enhance the presentation and can often lead to opportunitites to include additional material in the course. It has been my experience that even a disinterested, academically self-destructive student can fi nd something of sufficient interest in these excursions to grab their attention.

A good text on algorithms and one that merits a hard copy for the shelf!

An example of what to strive for when writing a textbook.

Comments are closed.