Algorithms

1st Edition
id: 323454 not VIP Open in MaM

By Umesh Vazirani, Christos Papadimitriou, Sanjoy Dasgupta

Language: English

Category: Ebook - Computer/Internet

Categories: Computer/Internet

Size: 1.9 MiB pdf Files: 1

Uploader: Pandread

Uploaded At: 2016-08-08 21:59:18

Algorithms, Computer Science. 1st edition 2006

Description

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.


Contents
Preface 9
0 Prologue 11
0.1 Books and algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.2 Enter Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
0.3 Big-O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1 Algorithms with numbers 21
1.1 Basic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3 Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5 Universal hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Randomized algorithms: a virtual chapter 38
2 Divide-and-conquer algorithms 51
2.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.4 Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.6 The fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3 Decompositions of graphs 87
3.1 Why graphs? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2 Depth-rst search in undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3 Depth-rst search in directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4 Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4 Paths in graphs 109
4.1 Distances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.2 Breadth-rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Lengths on edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.4 Dijkstra's algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.5 Priority queue implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.6 Shortest paths in the presence of negative edges . . . . . . . . . . . . . . . . . . . 122
4.7 Shortest paths in dags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5 Greedy algorithms 133
5.1 Minimum spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.2 Huffman encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
5.3 Horn formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.4 Set cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6 Dynamic programming 161
6.1 Shortest paths in dags, revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.2 Longest increasing subsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.3 Edit distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.4 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.5 Chain matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.6 Shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.7 Independent sets in trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7 Linear programming and reductions 189
7.1 An introduction to linear programming . . . . . . . . . . . . . . . . . . . . . . . . 189
7.2 Flows in networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.3 Bipartite matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
7.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5 Zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.6 The simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.7 Postscript: circuit evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
8 NP-complete problems 233
8.1 Search problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.2 NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.3 The reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Exercises . . . . . . . .

9 Coping with NP-completeness 269
9.1 Intelligent exhaustive search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.2 Approximation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
9.3 Local search heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
10 Quantum algorithms 295
10.1 Qubits, superposition, and measurement . . . . . . . . . . . . . . . . . . . . . . . 295
10.2 The plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.3 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
10.5 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
10.6 Factoring as periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.7 The quantum algorithm for factoring . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
Historical notes and further reading 313
Index

Other Torrents