Contents xv Important Concepts,Formulas,and Theorems 289 Problems 290 5.4 Random Variables 292 What Are Random Variables? 292 Binomial Probabilities 293 A Taste of Generating Functions 295 Expected Value 296 Expected Values of Sums and Numerical Multiples 299 Indicator Random Variables 302 The Number of Trials until the First Success 304 Important Concepts,Formulas,and Theorems 306 Problems 307 5.5 Probability Calculations in Hashing 310 Expected Number of Items per Location 310 Expected Number of Empty Locations 311 Expected Number of Collisions 312 Expected Maximum Number of Elements in a Location of a Hash Table 315 Important Concepts,Formulas,and Theorems 320 Problems 321 5.6 Conditional Expectations,Recurrences, and Algorithms 325 When Running Times Depend on More than Size of Inputs 325 Conditional Expected Values 327 Randomized Algorithms 329 Selection Revisited 331 QuickSort 333 A More Careful Analysis of RandomSelect 336 Important Concepts,Formulas,and Theorems 339 Problems 340Contents xv Important Concepts, Formulas, and Theorems 289 Problems 290 5.4 Random Variables 292 What Are Random Variables? 292 Binomial Probabilities 293 A Taste of Generating Functions 295 Expected Value 296 Expected Values of Sums and Numerical Multiples 299 Indicator Random Variables 302 The Number of Trials until the First Success 304 Important Concepts, Formulas, and Theorems 306 Problems 307 5.5 Probability Calculations in Hashing 310 Expected Number of Items per Location 310 Expected Number of Empty Locations 311 Expected Number of Collisions 312 Expected Maximum Number of Elements in a Location of a Hash Table 315 Important Concepts, Formulas, and Theorems 320 Problems 321 5.6 Conditional Expectations, Recurrences, and Algorithms 325 When Running Times Depend on More than Size of Inputs 325 Conditional Expected Values 327 Randomized Algorithms 329 Selection Revisited 331 QuickSort 333 A More Careful Analysis of RandomSelect 336 Important Concepts, Formulas, and Theorems 339 Problems 340