文档介绍：Algorithms
Copyright c 2006 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani
July 18, 2006
2
Contents
Preface 9
0 Prologue 11
Books and algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Enter i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Big-O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1 Algorithms with numbers 21
Basic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Universal hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Randomized algorithms: a virtual chapter 38
2 Divide-and-conquer algorithms 51
Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
The fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3 positions of graphs 87