Algorithms

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 Cover Page Title Page Copyright Page Dedication Contents Preface 0 Prologue 0.1 Books and algorithms 0.2 Enter Fibonacci 0.3 Big-O notation Exercises 1 Algorithms with numbers 1.1 Basic arithmetic 1.2 Modular arithmetic 1.3 Primality testing 1.4 Cryptography 1.5 Universal hashing Exercises Randomized algorithms: a virtual chapter 2 Divide-and-conquer algorithms 2.1 Multiplication 2.2 Recurrence relations 2.3 Mergesort 2.4 Medians 2.5 Matrix multiplication 2.6 The fast Fourier transform Exercises 3 Decompositions of graphs 3.1 Why graphs? 3.2 Depth-first search in undirected graphs 3.3 Depth-first search in directed graphs 3.4 Strongly connected components Exercises 4 Paths in graphs 4.1 Distances 4.2 Breadth-first search 4.3 Lengths on edges 4.4 Dijkstra’s algorithm 4.5 Priority queue implementations 4.6 Shortest paths in the presence of negative edges 4.7 Shortest paths in dags Exercises 5 Greedy algorithms 5.1 Minimum spanning trees 5.2 Huffman encoding 5.3 Horn formulas 5.4 Set cover Exercises 6 Dynamic programming 6.1 Shortest paths in dags, revisited 6.2 Longest increasing subsequences 6.3 Edit distance 6.4 Knapsack 6.5 Chain matrix multiplication 6.6 Shortest paths 6.7 Independent sets in trees Exercises 7 Linear programming and reductions 7.1 An introduction to linear programming 7.2 Flows in networks 7.3 Bipartite matching 7.4 Duality 7.5 Zero-sum games 7.6 The simplex algorithm 7.7 Postscript: circuit evaluation Exercises 8 NP-complete problems 8.1 Search problems 8.2 NP-complete problems 8.3 The reductions Exercises 9 Coping with NP-completeness 9.1 Intelligent exhaustive search 9.2 Approximation algorithms 9.3 Local search heuristics Exercises 10 Quantum algorithms 10.1 Qubits, superposition, and measurement 10.2 The plan 10.3 The quantum Fourier transform 10.4 Periodicity 10.5 Quantum circuits 10.6 Factoring as periodicity 10.7 The quantum algorithm for factoring Exercises Historical notes and further reading Index Explaining the fundamentals of algorithms, this text emphasizes on understanding the mathematical idea behind each algorithm. It includes features such as: the use of boxes to strengthen the narrative: pieces that give historical context, descriptions of how the algorithms are used in practice, and excursions for the mathematically sophisticated.