xii Contents Implication 125 If and Only If 126 Important Concepts,Formulas,and Theorems 129 Problems 131 3.2 Variables and Quantifiers 133 Variables and Universes 133 Quantifiers 134 Standard Notation for Quantification 136 Statements about Variables 138 Rewriting Statements to Encompass Larger Universes 138 Proving Quantified Statements True or False 139 Negation of Quantified Statements 140 Implicit Quantification 143 Proof of Quantified Statements 144 Important Concepts,Formulas,and Theorems 145 Problems 147 3.3 Inference 149 Direct Inference (Modus Ponens)and Proofs 149 Rules of Inference for Direct Proofs 151 Contrapositive Rule of Inference 153 Proof by Contradiction 155 Important Concepts,Formulas,and Theorems 158 Problems 159 CHAPTER 4 Induction,Recursion, and Recurrences 161 4.1 Mathematical Induction 161 Smallest Counterexamples 161 The Principle of Mathematical Induction 165 Strong Induction 169 Induction in General 171 A Recursive View of Induction 173
xii Contents Implication 125 If and Only If 126 Important Concepts, Formulas, and Theorems 129 Problems 131 3.2 Variables and Quantifiers 133 Variables and Universes 133 Quantifiers 134 Standard Notation for Quantification 136 Statements about Variables 138 Rewriting Statements to Encompass Larger Universes 138 Proving Quantified Statements True or False 139 Negation of Quantified Statements 140 Implicit Quantification 143 Proof of Quantified Statements 144 Important Concepts, Formulas, and Theorems 145 Problems 147 3.3 Inference 149 Direct Inference (Modus Ponens) and Proofs 149 Rules of Inference for Direct Proofs 151 Contrapositive Rule of Inference 153 Proof by Contradiction 155 Important Concepts, Formulas, and Theorems 158 Problems 159 CHAPTER 4 Induction, Recursion, and Recurrences 161 4.1 Mathematical Induction 161 Smallest Counterexamples 161 The Principle of Mathematical Induction 165 Strong Induction 169 Induction in General 171 A Recursive View of Induction 173
Contents xiii Structural Induction 176 Important Concepts,Formulas,and Theorems 178 Problems 180 4.2 Recursion,Recurrences,and Induction 183 Recursion 183 Examples of First-Order Linear Recurrences 185 Iterating a Recurrence 187 Geometric Series 188 First-Order Linear Recurrences 191 Important Concepts,Formulas,and Theorems 195 Problems 197 4.3 Growth Rates of Solutions to Recurrences 198 Divide and Conquer Algorithms 198 Recursion Trees 201 Three Different Behaviors 209 Important Concepts,Formulas,and Theorems 210 Problems 212 4.4 The Master Theorem 214 Master Theorem 214 Solving More General Kinds of Recurrences 217 Extending the Master Theorem 218 Important Concepts,Formulas,and Theorems 220 Problems 221 4.5 More General Kinds of Recurrences 222 Recurrence Inequalities 222 The Master Theorem for Inequalities 223 A Wrinkle with Induction 225 Further Wrinkles in Induction Proofs 227 Dealing with Functions Other Than ne 230 Important Concepts,Formulas,and Theorems 232 Problems 233
Contents xiii Structural Induction 176 Important Concepts, Formulas, and Theorems 178 Problems 180 4.2 Recursion, Recurrences, and Induction 183 Recursion 183 Examples of First-Order Linear Recurrences 185 Iterating a Recurrence 187 Geometric Series 188 First-Order Linear Recurrences 191 Important Concepts, Formulas, and Theorems 195 Problems 197 4.3 Growth Rates of Solutions to Recurrences 198 Divide and Conquer Algorithms 198 Recursion Trees 201 Three Different Behaviors 209 Important Concepts, Formulas, and Theorems 210 Problems 212 4.4 The Master Theorem 214 Master Theorem 214 Solving More General Kinds of Recurrences 217 Extending the Master Theorem 218 Important Concepts, Formulas, and Theorems 220 Problems 221 4.5 More General Kinds of Recurrences 222 Recurrence Inequalities 222 The Master Theorem for Inequalities 223 A Wrinkle with Induction 225 Further Wrinkles in Induction Proofs 227 Dealing with Functions Other Than nc 230 Important Concepts, Formulas, and Theorems 232 Problems 233
xiv Contents 4.6 Recurrences and Selection 235 The Idea of Selection 235 A Recursive Selection Algorithm 236 Selection without Knowing the Median in Advance 237 An Algorithm to Find an Element in the Middle Half 239 An Analysis of the Revised Selection Algorithm 242 Uneven Divisions 244 Important Concepts,Formulas,and Theorems 246 Problems 247 CHAPTER 5 Probability 249 5.1 Introduction to Probability 249 Why Study Probability? 249 Some Examples of Probability Computations 252 Complementary Probabilities 253 Probability and Hashing 254 The Uniform Probability Distribution 256 Important Concepts,Formulas,and Theorems 259 Problems 260 5.2 Unions and Intersections 262 The Probability of a Union of Events 262 Principle of Inclusion and Exclusion for Probability 265 The Principle of Inclusion and Exclusion for Counting 271 Important Concepts,Formulas,and Theorems 273 Problems 274 5.3 Conditional Probability and Independence 276 Conditional Probability 276 Bayes'Theorem 280 Independence 280 Independent Trials Processes 282 Tree Diagrams 284 Primality Testing 288
xiv Contents 4.6 Recurrences and Selection 235 The Idea of Selection 235 A Recursive Selection Algorithm 236 Selection without Knowing the Median in Advance 237 An Algorithm to Find an Element in the Middle Half 239 An Analysis of the Revised Selection Algorithm 242 Uneven Divisions 244 Important Concepts, Formulas, and Theorems 246 Problems 247 CHAPTER 5 Probability 249 5.1 Introduction to Probability 249 Why Study Probability? 249 Some Examples of Probability Computations 252 Complementary Probabilities 253 Probability and Hashing 254 The Uniform Probability Distribution 256 Important Concepts, Formulas, and Theorems 259 Problems 260 5.2 Unions and Intersections 262 The Probability of a Union of Events 262 Principle of Inclusion and Exclusion for Probability 265 The Principle of Inclusion and Exclusion for Counting 271 Important Concepts, Formulas, and Theorems 273 Problems 274 5.3 Conditional Probability and Independence 276 Conditional Probability 276 Bayes’ Theorem 280 Independence 280 Independent Trials Processes 282 Tree Diagrams 284 Primality Testing 288
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 340
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 340
xvi Contents 5.7 Probability Distributions and Variance 343 Distributions of Random Variables 343 Variance 346 Important Concepts,Formulas,and Theorems 354 Problems 355 CHAPTER 6 Graphs 359 6.1 Graphs 359 The Degree of a Vertex 363 Connectivity 365 Cycles 367 Trees 368 Other Properties of Trees 368 Important Concepts,Formulas,and Theorems 371 Problems 373 6.2 Spanning Trees and Rooted Trees 375 Spanning Trees 375 Breadth-First Search 377 Rooted Trees 382 Important Concepts,Formulas,and Theorems 386 Problems 387 6.3 Eulerian and Hamiltonian Graphs 389 Eulerian Tours and Trails 389 Finding Eulerian Tours 394 Hamiltonian Paths and Cycles 395 NP-Complete Problems 401 Proving That Problems Are NP-Complete 403 Important Concepts,Formulas,and Theorems 406 Problems 407 6.4 Matching Theory 410 The Idea of a Matching 410 Making Matchings Bigger 414
xvi Contents 5.7 Probability Distributions and Variance 343 Distributions of Random Variables 343 Variance 346 Important Concepts, Formulas, and Theorems 354 Problems 355 CHAPTER 6 Graphs 359 6.1 Graphs 359 The Degree of a Vertex 363 Connectivity 365 Cycles 367 Trees 368 Other Properties of Trees 368 Important Concepts, Formulas, and Theorems 371 Problems 373 6.2 Spanning Trees and Rooted Trees 375 Spanning Trees 375 Breadth-First Search 377 Rooted Trees 382 Important Concepts, Formulas, and Theorems 386 Problems 387 6.3 Eulerian and Hamiltonian Graphs 389 Eulerian Tours and Trails 389 Finding Eulerian Tours 394 Hamiltonian Paths and Cycles 395 NP-Complete Problems 401 Proving That Problems Are NP-Complete 403 Important Concepts, Formulas, and Theorems 406 Problems 407 6.4 Matching Theory 410 The Idea of a Matching 410 Making Matchings Bigger 414