Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Front Cover
Cambridge University Press, Jan 31, 2005 - Computers - 352 pages
5 Reviews
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 2005 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, the probabilistic method and Markov chains. The second half covers more advanced topics such as continuous probability, applications of limited independence, entropy, Markov chain Monte Carlo methods 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 ratings

5 stars
2
4 stars
2
3 stars
1
2 stars
0
1 star
0

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.

Review: Probability and Computing: Randomized Algorithms and Probabilistic Analysis

User Review  - Goodreads

This book is an okay introduction to probabilistic algorithms. However, the problems sets are nigh-impossible with out a strong background in probability (certainly nothing in the book helps in doing ... Read full review

Contents

II
1
III
3
IV
8
V
12
VI
14
VII
20
VIII
22
IX
23
LXXVIII
177
LXXIX
182
LXXX
188
LXXXI
191
LXXXII
193
LXXXIII
194
LXXXIV
196
LXXXV
197

X
25
XI
26
XII
30
XIII
32
XIV
34
XV
38
XVI
44
XVII
45
XVIII
48
XX
50
XXI
52
XXII
53
XXIII
54
XXIV
57
XXV
61
XXVI
63
XXVIII
67
XXX
69
XXXI
71
XXXII
72
XXXIII
73
XXXIV
78
XXXV
83
XXXVI
90
XXXVII
92
XXXVIII
93
XXXIX
94
XL
98
XLI
99
XLII
104
XLIII
106
XLIV
107
XLV
109
XLVI
111
XLVII
112
XLVIII
113
XLIX
119
L
124
LI
126
LII
128
LIII
129
LIV
130
LV
131
LVI
133
LVIII
134
LX
135
LXI
136
LXII
138
LXIII
141
LXIV
142
LXVI
143
LXVII
146
LXVIII
148
LXIX
153
LXX
156
LXXI
159
LXXII
163
LXXIII
166
LXXIV
167
LXXV
173
LXXVI
174
LXXVII
176
LXXXVI
199
LXXXVII
201
LXXXVIII
204
LXXXIX
205
XC
207
XCI
210
XCII
212
XCIII
213
XCIV
216
XCVI
219
XCVII
225
XCVIII
228
XCIX
230
C
234
CI
237
CII
245
CIII
252
CIV
255
CVI
257
CVII
259
CVIII
263
CIX
265
CX
267
CXI
270
CXII
271
CXIII
274
CXIV
275
CXV
276
CXVI
277
CXVII
278
CXVIII
281
CXIX
282
CXX
286
CXXI
289
CXXII
295
CXXIII
297
CXXIV
299
CXXV
300
CXXVI
303
CXXVII
305
CXXVIII
307
CXXIX
308
CXXXI
309
CXXXII
314
CXXXIII
315
CXXXIV
316
CXXXV
317
CXXXVI
318
CXXXVII
319
CXXXVIII
321
CXXXIX
323
CXL
324
CXLI
326
CXLII
328
CXLIII
333
CXLIV
336
CXLV
341
CXLVI
344
CXLVIII
345
CL
349
CLI
350
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

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