Fundamentals of discrete math for computer science : a problem-solving primer

목차 (Table of Contents)

• CONTENTS
• 1 Algorithms, Numbers, and Machines = 1
• 1.1 What Is an Algorithm? = 4
• 1.2 Integer Algorithms and Complexity = 8
• 1.2.1 Prime Testing = 9
• 1.2.2 Real Numbers = 11
• 1.2.3 More Prime Testing = 12
• 1.2.4 Prime Factorization = 14
• 1.2.5 Logarithms = 16
• 1.2.6 Greatest Common Divisor = 18
• 1.3 Machine Representation of Numbers = 21
• 1.3.1 Approximation Errors = 23
• 1.3.2 Base 2, 8, and 16 = 26
• 1.4 Numerical Solutions = 35
• 1.4.1 Newton's Method for Square Roots = 35
• 1.4.2 The Bisection Algorithm = 37
• Exercises = 41
• 2 Sets, Sequences, and Counting = 45
• 2.1 Naïve Set Theory = 45
• 2.1.1 The Diabolical Librarian = 48
• 2.1.2 Operations on Sets and Cardinality = 49
• 2.1.3 The Pigeonhole Principle = 51
• 2.2 Sequences = 53
• 2.2.1 The Characteristic Sequence of a Subset = 55
• 2.3 Counting = 56
• 2.3.1 Number of k-Sequences on an n-Set = 57
• 2.3.2 Number of Subsets of an n-Set = 58
• 2.3.3 Number of k-Permutations on an n-Set = 58
• 2.3.4 n-Factorial = 59
• 2.3.5 Number of k-Subsets of an n-Set = 60
• 2.3.6 Pascal’s Triangle = 63
• 2.3.7 Counting Algorithmically (Without a Formula) = 66
• 2.4 Infinite Sequences and Complexity Functions = 69
• 2.4.1 The Towers of Hanoi = 72
• 2.4.2 Bad Complexity Functions = 75
• Exercises = 76
• 3 Boolean Expressions, Logic, and Proof = 81
• 3.1 The Greedy Algorithm and Three Cookie Problems = 81
• 3.1.1 The Greedy Algorithm = 82
• 3.2 Boolean Expressions and Truth Tables = 86
• 3.2.1 The Negation Operator = 86
• 3.2.2 The Conjunction Operator = 86
• 3.2.3 The Disjunction Operator = 87
• 3.2.4 The Conditional Operator = 89
• 3.2.5 The Biconditional Operator = 91
• 3.3 Predicates and Quantifiers = 92
• 3.4 Valid Arguments = 93
• 3.5 Examples of Proofs = 97
• 3.5.1 Direct Proof = 100
• 3.5.2 Indirect Proof = 101
• 3.5.3 Cantor’s Diagonalization Process = 104
• 3.6 Mathematical Induction = 106
• 3.6.1 Strong Induction = 117
• 3.7 Proofs Promised in Chap. 1 = 119
• 3.7.1 Russian Peasant Multiplication Is Correct = 119
• 3.7.2 Resolving the Cake Cutting Conundrum = 121
• 3.7.3 Casting Out Nines = 123
• 3.7.4 Euclid's Algorithm for GCD Is Correct = 125
• 3.8 The Proof Promised in Chap. 2 = 128
• Exercises = 130
• 4 Searching and Sorting = 137
• 4.1 Searching = 137
• 4.1.1 Searching an Arbitrary List = 137
• 4.1.2 Searching a Sorted List = 139
• 4.2 Branching Diagrams = 145
• 4.2.1 A Second Version of Binary Search = 145
• 4.3 Sorting = 153
• 4.3.1 Selection Sorts = 153
• 4.3.2 Exchange Sorts = 156
• 4.4 Binary Trees with (at Least) n! Leaves = 163
• 4.5 Partition Sorts = 171
• 4.6 Comparison of Sorting Algorithms = 184
• 4.6.1 Timings and Operation Counts = 184
• Exercises = 185
• 5 Graphs and Trees = 191
• 5.1 Introduction = 191
• 5.1.1 Degrees = 196
• 5.1.2 Eulerian Graphs = 196
• 5.1.3 Hamiltonian Graphs = 197
• 5.2 Paths, Circuits, and Polygons = 198
• 5.2.1 Subgraphs Determined by Paths = 200
• 5.3 Trees = 202
• 5.3.1 Traversals = 203
• 5.4 Edge-Weighted Graphs = 217
• 5.4.1 Shortest Paths = 221
• 5.5 Drawing and Coloring = 222
• 5.5.1 Bipartite Graphs = 223
• 5.5.2 Planar Graphs = 225
• 5.5.3 Some History of the Four Color Theorem = 232
• Exercises = 233
• 6 Directed Graphs = 241
• 6.1 Introducing Directions = 241
• 6.2 Strong Connectivity = 243
• 6.3 Topological Sorting = 247
• 6.4 Shortest Paths in Digraphs (Acyclic or not) = 258
• 6.4.1 Distance Function = 259
• 6.4.2 Dijkstra's Algorithm = 259
• 6.4.3 Floyd-Warshall Algorithm = 267
• 6.5 The Maximum Flow Problem = 272
• 6.6 Matchings in Bipartite Graphs = 284
• Exercises = 291
• 7 Relations: Especially on (Integer) Sequences = 299
• 7.1 Relations and Representations = 299
• 7.1.1 Matrix Representation = 300
• 7.1.2 Directed Graph Representation = 301
• 7.1.3 Properties of Relations = 301
• 7.2 Equivalence Relations = 302
• 7.2.1 Matrix and Digraph of an Equivalence Relation = 303
• 7.3 Order Relations = 306
• 7.3.1 Matrix and Digraph of a Partial Order = 307
• 7.3.2 Minimal and Maximal Elements = 308
• 7.4 Relations on Finite Sequences = 311
• 7.4.1 Domination = 311
• 7.4.2 Lexicographic Order = 313
• 7.5 Relations on Infinite Sequences = 315
• 7.5.1 Asymptotic Dominance and Big-Oh Notation = 316
• 7.5.2 Asymptotic Equivalence and Big-Theta Notation = 322
• 7.5.3 Asymptotic Ranking = 325
• 7.5.4 Strong Asymptotic Dominance and Little-Oh Notation = 326
• Exercises = 328
• 8 Sequences and Series = 333
• 8.1 Examples Defined by Recurrence Equations = 334
• 8.2 Solving First-Order Linear Recurrence Equations = 340
• 8.3 The Fibonacci Sequence = 346
• 8.3.1 Algorithms for the Fibonacci Sequence = 348
• 8.3.2 The Golden Ratio = 350
• 8.3.3 The Fibonacci Sequence and the Golden Ratio = 351
• 8.3.4 The Order of the Fibonacci Sequence = 354
• 8.3.5 The Complexity of Euclid’s Algorithm for GCD = 355
• 8.4 Solving Second-Order Linear Recurrence Equations = 358
• 8.5 Infinite Series = 366
• 8.5.1 Zeno's Paradoxes = 366
• 8.5.2 Formal Definitions of Convergence of Sequences and Series = 367
• Exercises = 373
• 9 Generating Sequences and Subsets = 379
• 9.1 Generating Sequences in Lexicographic-Order = 381
• 9.2 Generating All k-Sequences on {1..n} = 384
• 9.2.1 Average-Case Complexity = 384
• 9.3 Generating Subsets of {1..n} as Increasing Sequences = 388
• 9.4 Generating Permutations in Lexicographic-Order = 398
• 9.4.1 Generating All k-Permutations of {1..n} in Lex-Order = 407
• Exercises = 412
• 10 Discrete Probability and Average-Case Complexity = 421
• 10.1 Probabilistic Models = 421
• 10.1.1 Sample Spaces = 422
• 10.1.2 Probability Functions = 422
• 10.1.3 The Special Case of Equally Likely Outcomes = 424
• 10.2 Conditional Probability = 427
• 10.2.1 Combinations of Events = 428
• 10.2.2 Conditional Probability = 428
• 10.2.3 Independent Events = 430
• 10.2.4 Mutually Exclusive Events = 430
• 10.3 Random Variables and Expected Values = 435
• 10.3.1 Expected Frequency = 436
• 10.3.2 Expected Values = 437
• 10.3.3 Probability Distributions = 438
• 10.4 Standard Distributions and Their Expected Values = 439
• 10.4.1 The Uniform Distribution = 439
• 10.4.2 The Binomial Distribution = 443
• 10.4.3 The Geometric Distribution = 444
• 10.5 Conditional Expected Values = 447
• 10.5.1 Conditional Expectation = 452
• 10.6 Average-Case Complexity = 454
• 10.6.1 Applying Expectation to Linear Search = 454
• 10.6.2 Applying Expectation to QuickSort = 455
• Exercises = 460
• 11 Turing Machines = 467
• 11.1 What Is an Algorithm? = 468
• 11.1.1 The Church-Turing Thesis = 475
• 11.1.2 Universal Turing Machine: As a Computational Model = 476
• 11.1.3 The Halting Problem = 476
• Exercises = 479
• Appendix A : Solutions to Selected Exercises = 483
• Index = 509