Fundamentals of Discrete Math for Computer Science – Brock University & University of Calgary (Undergraduate Topics in Computer Science, 2013) – Complete Problem-Solving Primer

This textbook introduces the essential principles of discrete mathematics with a strong emphasis on computer science applications. It covers fundamental topics such as algorithms, sets, logic, proofs, counting, graphs, trees, relations, recursion, generating functions, probability, and Turing machines. Each chapter begins with real-world computational examples and includes detailed walkthroughs, exercises, and algorithmic analyses. Designed for undergraduate computer science students, the material blends theoretical rigor with practical problem-solving techniques, serving as both a learning and reference resource. 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 ................... ...................... 43 2.1 Na¨ıve Set Theory ............................. ...................... 43 2.1.1 The Diabolical Librarian............. ....................... 46 2.1.2 Operations on Sets and Cardinality. . ....................... 47 2.1.3 The Pigeonhole Principle ............ ....................... 49 2.2 Sequences ..................................... ...................... 51 2.2.1 The Characteristic Sequence of a Subset ................... 53 2.3 Counting....................................... ...................... 54 2.3.1 Number of k-Sequences on an n-Set. ....................... 55 2.3.2 Number of Subsets of an n-Set ...... ....................... 56 2.3.3 Number of k-Permutations on an n-Set..................... 56 2.3.4 n-Factorial............................ ....................... 57 2.3.5 Number of k-Subsets of an n-Set .... ....................... 58 2.3.6 Pascal’s Triangle ..................... ....................... 61 2.3.7 Counting Algorithmically (Without a Formula)............ 64 ix 2.4 Infinite Sequences and Complexity Functions 67 2.4.1 The Towers of Hanoi 70 2.4.2 Bad Complexity Functions 73 Exercises 74 3 Boolean Expressions, Logic, and Proof 77 3.1 The Greedy Algorithm and Three Cookie Problems 77 3.1.1 The Greedy Algorithm 78 3.2 Boolean Expressions and Truth Tables 82 3.2.1 The Negation Operator 82 3.2.2 The Conjunction Operator 82 3.2.3 The Disjunction Operator 83 3.2.4 The Conditional Operator 85 3.2.5 The Biconditional Operator 87 3.3 Predicates and Quantifiers 88 3.4 Valid Arguments 89 3.5 Examples of Proofs 93 3.5.1 Direct Proof 96 3.5.2 Indirect Proof 97 3.5.3 Cantor’s Diagonalization Process 100 3.6 Mathematical Induction 102 3.6.1 Strong Induction 113 3.7 Proofs Promised in Chap. 1 115 3.7.1 Russian Peasant Multiplication Is Correct 115 3.7.2 Resolving the Cake Cutting Conundrum 117 3.7.3 Casting Out Nines 119 3.7.4 Euclid’s Algorithm for GCD Is Correct 121 3.8 The Proof Promised in Chap. 2 124 Exercises 126 4 Searching and Sorting 131 4.1 Searching 131 4.1.1 Searching an Arbitrary List 131 4.1.2 Searching a Sorted List 133 4.2 Branching Diagrams 139 4.2.1 A Second Version of Binary Search 139 4.3 Sorting 147 4.3.1 Selection Sorts 147 4.3.2 Exchange Sorts 150 4.4 Binary Trees with (at Least) n! Leaves 157 4.5 Partition Sorts 165 4.6 Comparison of Sorting Algorithms 178 4.6.1 Timings and Operation Counts 178 Exercises 179 Contents xi 5 Graphs and Trees ................................. ...................... 183 5.1 Introduction ................................... ...................... 183 5.1.1 Degrees............................... ....................... 188 5.1.2 Eulerian Graphs ...................... ....................... 188 5.1.3 Hamiltonian Graphs.................. ....................... 189 5.2 Paths, Circuits, and Polygons ................. ...................... 190 5.2.1 Subgraphs Determined by Paths ..... ....................... 192 5.3 Trees. . . ........................................ ...................... 194 5.3.1 Traversals ............................ ....................... 195 5.4 Edge-Weighted Graphs ....................... ...................... 209 5.4.1 Shortest Paths ........................ ....................... 213 5.5 Directed Graphs ............................... ...................... 214 5.5.1 Dipaths ............................... ....................... 215 5.5.2 Distance Function .................... ....................... 216 5.5.3 Dijkstra’s Algorithm ................. ....................... 217 5.5.4 Floyd-Warshall Algorithm ........... ....................... 224 Exercises .... ........................................ ...................... 229 6 Relations: Especially on (Integer) Sequences ... ...................... 233 6.1 Relations and Representations ................ ...................... 233 6.1.1 Matrix Representation ............... ....................... 234 6.1.2 Directed Graph Representation ...... ....................... 235 6.1.3 Properties of Relations ............... ....................... 235 6.2 Equivalence Relations ........................ ...................... 236 6.2.1 Matrix and Digraph of an Equivalence Relation ........... 237 6.3 Order Relations ............................... ...................... 240 6.3.1 Matrix and Digraph of a Partial Order. ..................... 241 6.3.2 Minimal and Maximal Elements..... ....................... 242 6.4 Relations on Finite Sequences ................ ...................... 245 6.4.1 Domination........................... ....................... 245 6.4.2 Lexicographic Order ................. ....................... 247 6.5 Relations on Infinite Sequences .............. ...................... 249 6.5.1 Asymptotic Dominance and Big-Oh Notation ............. 250 6.5.2 Asymptotic Equivalence and Big-Theta Notation.......... 256 6.5.3 Asymptotic Ranking ................. ....................... 259 6.5.4 Strong Asymptotic Dominance and Little-Oh Notation.... 260 Exercises .... ........................................ ...................... 262 7 Sequences and Series .............................. ...................... 265 7.1 Examples Defined by Recurrence Equations . ...................... 266 7.2 Solving First-Order Linear Recurrence Equations ................. 272 7.3 The Fibonacci Sequence ...................... ...................... 278 7.3.1 Algorithms for the Fibonacci Sequence .................... 280 7.3.2 The Golden Ratio .................... ....................... 282 7.3.3 The Fibonacci Sequence and the Golden Ratio ............ 283 7.3.4 The Order of the Fibonacci Sequence ...................... 286 7.3.5 The Complexity of Euclid’s Algorithm for GCD .......... 287 7.4 Solving Second-Order Linear Recurrence Equations .............. 290 7.5 Infinite Series 298 7.5.1 Zeno’s Paradoxes 298 7.5.2 Formal Definitions of Convergence of Sequences and Series 299 Exercises 305 8 Generating Sequences and Subsets 311 8.1 Generating Sequences in Lexicographic-Order 313 8.2 Generating All k-Sequences on {1..n} 316 8.2.1 Average-Case Complexity 316 8.3 Generating Subsets of {1..n} as Increasing Sequences 320 8.4 Generating Permutations in Lexicographic-Order 330 8.4.1 Generating All k-Permutations of {1..n} in Lex-Order 338 Exercises 343 9 Discrete Probability and Average-Case Complexity 351 9.1 Probabilistic Models 351 9.1.1 Sample Spaces 352 9.1.2 Probability Functions 352 9.1.3 The Special Case of Equally Likely Outcomes 354 9.2 Conditional Probability 357 9.2.1 Combinations of Events 358 9.2.2 Conditional Probability 358 9.2.3 Independent Events 360 9.2.4 Mutually Exclusive Events 360 9.3 Random Variables and Expected Values 365 9.3.1 Expected Frequency 366 9.3.2 Expected Values 367 9.3.3 Probability Distributions 368 9.4 Standard Distributions and Their Expected Values 369 9.4.1 The Uniform Distribution 369 9.4.2 The Binomial Distribution 373 9.4.3 The Geometric Distribution 374 9.5 Conditional Expected Values 377 9.5.1 Conditional Expectation 382 9.6 Average-Case Complexity 384 9.6.1 Applying Expectation to Linear Search 384 9.6.2 Applying Expectation to QuickSort 385 Exercises 390 10 Turing Machines 397 10.1 What Is an Algorithm? 398 10.1.1 The Church-Turing Thesis. 405 10.1.2 Universal Turing Machine: As a Computational Model 406 10.1.3 The Halting Problem 406 Exercises 409 Index 413