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

McGraw-Hill Higher Education, 2008. - 332 pages.This text 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.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 coveres 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.Prologue
Books and algorithms
Enter Fibonacci
Big-0 notation
Exercises
Algorithms with numbers
Basic arithmetic
Modular arithmetic
Primality testing
Cryptography
Universal hashing
Exercises
Randomized algorithms: a virtual chapter
Divide-and-conquer algorithms
Multiplication
Recurrence relations
Mergesort
Medians
Matrix multiplication
The fast Fourier transform
Exercises
Decompositions of graphs
Why graphs?
Depth-first search in undirected graphs
Depth-first search in directed graphs
Strongly connected components
Exercises
Paths in graphs
Distances
Breadth-first search
Lengths on edges
Dijkstra’s algorithm
Priority queue implementations
Shortest paths in the presence of negative edges
Shortest paths in dags
Exercises
Greedy algorithms
Minimum spanning trees
Huffman encoding
Horn formulas
Set cover
Exercises
Dynamic programming
Shortest paths in dags, revisited
Longest increasing subsequences
Edit distance
Knapsack
Chain matrix multiplication
Shortest paths
Independent sets in trees
Exercises
Linear programming and reductions
An introduction to linear programming
Flows in networks
Bipartite matching
Duality
Zero-sum games
The simplex algorithm
Postscript: circuit evaluation
Exercises
NP-complete problems
Search problems
NP-complete problems
The reductions
Exercises
Coping with NP-completeness
Intelligent exhaustive search
Approximation algorithms
Local search heuristics
Exercises
Quantum algorithms
Qubits, superposition, and measurement
The plan
The quantum Fourier transform
Periodicity
Quantum circuits
Factoring as periodicity
The quantum algorithm for factoring
Exercises
Historical notes and further reading