Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Front Cover
Cambridge University Press, Jan 31, 2005 - Computers - 352 pages
Randomization and probabilistic techniques play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols. This textbook is designed to accompany a one- or two-semester course for advanced undergraduates or beginning graduate students in computer science and applied mathematics. It gives an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It assumes only an elementary background in discrete mathematics and gives a rigorous yet accessible treatment of the material, with numerous examples and applications. The first half of the book covers core material, including random sampling, expectations, Markov's inequality, Chevyshev's inequality, Chernoff bounds, balls and bins models, the probabilistic method, and Markov chains. In the second half, the authors delve into more advanced topics such as continuous probability, applications of limited independence, entropy, Markov chain Monte Carlo methods, coupling, martingales, and balanced allocations. With its comprehensive selection of topics, along with many examples and exercises, this book is an indispensable teaching tool.
 

What people are saying - Write a review

User Review - Flag as inappropriate

Excellent book. Lower level than Motwani Raghavan; so, good for raw beginners. Section on routing on butterfly network not clear to me. Other parts were fine.

Contents

II
1
V
3
VI
8
VII
12
VIII
14
IX
20
XI
22
XII
23
LXXXIX
177
XC
182
XCI
188
XCIV
191
XCV
193
XCVI
194
XCVII
196
XCVIII
197

XIII
25
XIV
26
XV
30
XVI
32
XVII
34
XVIII
38
XIX
44
XXII
45
XXIII
48
XXIV
50
XXV
52
XXVI
53
XXVII
54
XXVIII
57
XXIX
61
XXXII
63
XXXIII
67
XXXV
69
XXXVI
71
XXXVII
72
XXXVIII
73
XXXIX
78
XL
83
XLI
90
XLIV
92
XLV
93
XLVI
94
XLVII
98
XLVIII
99
XLIX
104
L
106
LI
107
LII
109
LIII
111
LIV
112
LV
113
LVI
119
LVII
124
LVIII
126
LXI
128
LXII
129
LXIII
130
LXIV
131
LXV
133
LXVII
134
LXIX
135
LXX
136
LXXI
138
LXXII
141
LXXIII
142
LXXV
143
LXXVI
146
LXXVII
148
LXXVIII
153
LXXXI
156
LXXXII
159
LXXXIII
163
LXXXIV
166
LXXXV
167
LXXXVI
173
LXXXVII
174
LXXXVIII
176
XCIX
199
C
201
CI
204
CII
205
CIII
207
CIV
210
CV
212
CVI
213
CVII
216
CIX
219
CX
225
CXI
228
CXII
230
CXIII
234
CXIV
237
CXV
245
CXVI
252
CXVIII
255
CXX
257
CXXI
259
CXXII
263
CXXIII
265
CXXIV
267
CXXV
270
CXXVI
271
CXXIX
274
CXXX
275
CXXXI
276
CXXXII
277
CXXXIII
278
CXXXIV
281
CXXXV
282
CXXXVI
286
CXXXVII
289
CXXXVIII
295
CXXXIX
297
CXL
299
CXLI
300
CXLII
303
CXLIII
305
CXLIV
307
CXLV
308
CXLVII
309
CXLVIII
314
CLI
315
CLII
316
CLIII
317
CLIV
318
CLV
319
CLVI
321
CLVII
323
CLVIII
324
CLIX
326
CLX
328
CLXI
333
CLXII
336
CLXIII
341
CLXIV
344
CLXVI
345
CLXVIII
349
CLXIX
350
Copyright

Other editions - View all

Common terms and phrases

About the author (2005)

Michael Miztenmacher is a John L. Loeb Associate Professor in Computer Science at Harvard University. Having written nearly 100 articles on a variety of topics in computer science, his research focuses on randomized algorithms and networks. He has received an NSF CAREER Award and an Alfred P. Sloan Research Fellowship. In 2002, he shared the IEEE Information Theory Society Best Paper Award for his work on error-correcting codes.

Eli Upfal is Professor and Chair of Computer Science at Brown University. He has published more than 100 papers in refereed journals and professional conferences, and is the inventor of more than ten patents. His main research interests are randomized computation and probabilistic analysis of algorithms, with applications to optimization algorithms, communication networks, parallel and distributed computing and computational biology.

Bibliographic information