Submitted by: Submitted by imsarranjan
Views: 10
Words: 123015
Pages: 493
Category: Science and Technology
Date Submitted: 09/12/2015 09:05 PM
Algorithms
Copyright c 2006 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani
July 18, 2006
2
Algorithms
Contents
Preface
0 Prologue
0.1 Books and algorithms
0.2 Enter Fibonacci . . .
0.3 Big-O notation . . . .
Exercises . . . . . . . . . .
9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
12
15
18
1 Algorithms with numbers
1.1 Basic arithmetic . . . . .
1.2 Modular arithmetic . . .
1.3 Primality testing . . . .
1.4 Cryptography . . . . . .
1.5 Universal hashing . . . .
Exercises . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
21
25
33
39
43
48
.
.
.
.
Randomized algorithms: a virtual chapter
39
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 . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
55
55
58
60
64
66
68
83
.
.
.
.
.
91
91
93
98
101
106
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
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 . . . . . . . . . . . . . . . . . . ....