This textbook explains the fundamentals of algorithms in a storyline that makes the text enjoyable and easy to digest. The emphasis is mostly placed on understanding the crisp mathematical idea behind each algorithm in a manner that is intuitive and rigorous without being unduly formal. An accessible treatment of linear programming introduces students to one of the greatest achievements in algorithms. A chapter on the Quantum Algorithm for factoring has also been added that provides a unique peephole into this exciting topic.
Pedagogical features, such as the use of the three series of separate boxes have been introduced in the book to strengthen its narrative. These pieces provide historical context, a description of how the algorithms are used in practice, and excursions for the mathematically sophisticated.
Salient Features:
1. The book is concise and realistic; with key Design Issues and rationales that clearly outline the problems to be solved. It shows how to develop appealing algorithms to achieve desired results.
2. Small book on Algorithms covering most of the topics in the area.
3. The book also covers interesting stories about the development of important algorithms and their current uses in the global information environment.
About the Author
Sanjoy Dasgupta received the Ph.D. degree from University of California at Berkeley, Berkeley, CA, USA, in 2000.,He spent two years at the AT&T Research Labs, Florham Park, NJ, USA. He is currently a Professor with the Department of Computer Science and Engineering, University of California at San Diego, San Diego, CA, USA. His current research interest includes algorithmic statistics, with a focus on unsupervised and minimally supervised learning. Dr. Dasgupta was a Program Co-Chair of the Conference on Learning Theory in 2009 and of the International Conference on Machine Learning in 2013.
Christos Papadimitriou was born and raised in Athens, Greece, and studied in Athens and at Princeton. He has taught Computer Science at Harvard, MIT, Stanford, and, since 1996, at Berkeley, where he is the C. Lester Hogan Professor of Computer Science. In his research he uses mathematics to understand the power and limitations of computers. He is a member of the National Academy of Sciences, the American Academy of Arts and Sciences, and the National Academy of Engineering. He has written several of the standard textbooks in algorithms and computation, and three novels: "Turing," "Logicomix" (with Apostolos Doxiadis, art by Alecos Papadatos and Annie di Donna), and "Independence" (2017).
TABLE OF CONTENTS:
Chapter 0: Prologue
Chapter 1: Algorithms with Numbers
Randomized Algorithms: A Virtual Chapter
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 and Reductions
Chapter 8: NP-Complete Problems
Chapter 9: Coping With NP-Completeness
Chapter 10: Quantum Algorithms
Historical Notes & Further Reading
Index
