Randomness is a powerful phenomenon that can be harnessed to solve various problems in all areas of computer science. Randomized algorithms are often more efficient, simpler and, surprisingly, also more reliable than their deterministic counterparts. Computing tasks exist that require billions of years of computer work when solved using the fastest known deterministic algorithms, but they can be solved using randomized algorithms in a few minutes with negligible error probabilities.
Introducing the fascinating world of randomness, this book systematically teaches the main algorithm design paradigms – foiling an adversary, abundance of witnesses, fingerprinting, amplification, and random sampling, etc. – while also providing a deep insight into the nature of success in randomization. Taking sufficient time to present motivations and to develop the reader's intuition, while being rigorous throughout, this text is a very effective and efficient introduction to this exciting field.
Author(s): Juraj Hromkovič
Series: Texts in Theoretical Computer Science. An EATCS Series
Publisher: Springer
Year: 2005
Language: English
Pages: 290
Cover
......Page 1
Series
......Page 2
Title: Design and analysis of randomized algorithms
......Page 4
Copyright
......Page 5
Preface......Page 10
Contents......Page 12
1.
Introduction......Page 14
A.1 Objectives......Page 0
1.2 Randomness as a Source of Efficiency –
an Exemplary Application......Page 18
1.3 Concept of the Book......Page 24
1.4 To the Student......Page 27
1.5 To the Teacher......Page 29
2.
Fundamentals......Page 32
2.2 Elementary Probability Theory......Page 33
2.3 Models of Randomized Algorithms......Page 50
2.4 Classification of Randomized Algorithms......Page 64
2.5 Classification of Randomized Algorithms for Optimization Problems
......Page 85
2.6 Paradigms of the Design of Randomized Algorithms......Page 100
2.7 Summary......Page 109
3.
Foiling the Adversary......Page 114
3.2 Hashing......Page 115
3.3 Universal Hashing......Page 122
3.4 Online Algorithms......Page 129
3.5 Randomized Online Algorithms......Page 133
3.6 Summary......Page 141
4. Fingerprinting
......Page 144
4.2 Communication Protocols......Page 146
4.3 The Substring Problem......Page 152
4.4 Verification of Matrix Multiplication......Page 154
4.5 Equivalence of Two Polynomials......Page 157
4.6 Summary......Page 162
5. Success Amplification and Random Sampling
......Page 166
5.2 Efficient Amplification by Repeating Critical Computation Parts
......Page 167
5.3 Repeated Random Sampling and Satisfiability......Page 179
5.4 Random Sampling and Generating Quadratic
Nonresidues......Page 187
5.5 Summary......Page 194
6. Abundance of Witnesses
......Page 196
6.2 Searching for Witnesses for Primality Testing......Page 197
6.3 Solovay-Strassen Algorithm for Primality Testing......Page 205
6.4 Generation of Random Primes......Page 215
6.5 Summary......Page 219
7. Optimization and Random Rounding
......Page 222
7.2 Relaxation to Linear Programming......Page 223
7.3 Random Rounding and MAX-SAT......Page 229
7.4 Combining Random Sampling and Random Rounding
......Page 235
7.5 Summary......Page 238
A. Fundamentals of Mathematics
......Page 240
A.2 Algebra and Number Theory......Page 241
A.3 Combinatorics......Page 269
A.4 Summary......Page 277
References......Page 280
Index......Page 284
