Practical Discrete Mathematics: Discover math principles that fuel algorithms for computer science and machine learning with Python

Practical Discrete Mathematics....2 Why subscribe?....4 Contributors....5 About the authors....5 About the reviewer....6 Packt is searching for authors like you....7 Preface....45 Who this book is for....46 What this book covers....47 Part I – Basic Concepts of Discrete Math....48 Part II – Implementing Discrete Mathematics in Data and Computer Science....49 Part III – Real-World Applications of Discrete Mathematics....50 To get the most out of this book....50 Download the example code files....52 Download the color images....52 Conventions used....52 Get in touch....53 Reviews....54 Part I – Basic Concepts of Discrete Math....55 Chapter 1: Key Concepts, Notation, Set Theory, Relations, and Functions....56 What is discrete mathematics?....57 Elementary set theory....60 Definition–Sets and set notation....61 Definition: Elements of sets....61 Definition: The empty set....61 Example: Some examples of sets....61 Definition: Subsets and supersets....62 Definition: Set-builder notation....62 Example: Using set-builder notation....63 Definition: Basic set operations....64 Definition: Disjoint sets....67 Example: Even and odd numbers....67 Theorem: De Morgan's laws....67 Example: De Morgan's Law....69 Definition: Cardinality....70 Example: Cardinality....70 Functions and relations....70 Definition: Relations, domains, and ranges....71 Definition: Functions....71 Examples: Relations versus functions....72 Example: Functions in elementary algebra....72 Example: Python functions versus mathematical functions....74 Summary....76 Chapter 2: Formal Logic and Constructing Mathematical Proofs....78 Formal Logic and Proofs by Truth Tables....79 Basic Terminology for Formal Logic....80 Example – an invalid argument....82 Example – all penguins live in South Africa!....83 Cores Ideas in Formal Logic....86 Truth Tables....89 Example – The Converse....91 Example – Transitivity Law of Conditional Logic....93 Example – De Morgan's Laws....95 Example – The Contrapositive....97 Direct Mathematical Proofs....99 Example – Products of Even and Odd Integers....100 Example – roots of even numbers....101 Shortcut – The Contrapositive....103 Proof by Contradiction....104 Example – is there a smallest positive rational number?....107 Example – Prove is an Irrational Number....108 Example – How Many Prime Numbers Are There?....110 Proof by mathematical induction....113 Example – Adding 1 + 2 + … + n....114 Example – Space-Filling Shapes....118 Example – exponential versus factorial growth....120 Summary....123 Chapter 3: Computing with Base-n Numbers....124 Understanding base-n numbers....125 Example – Decimal numbers....125 Definition – Base-n numbers....127 Converting between bases....127 Converting base-n numbers to decimal numbers....128 Example – Decimal value of a base-6 number....128 Base-n to decimal conversion....128 Example – Decimal to base-2 (binary) conversion....129 Example – Decimal to binary and hexadecimal conversions in Python....130 Binary numbers and their applications....131 Boolean algebra....134 Example – Netflix users....140 Hexadecimal numbers and their application....144 Example – Defining locations in computer memory....147 Example – Displaying error messages....150 Example – Media Access Control (MAC) addresses....150 Example – Defining colors on the web....151 Summary....153 Chapter 4: Combinatorics Using SciPy....154 The fundamental counting rule....155 Definition – the Cartesian product....155 Theorem – the cardinality of Cartesian products of finite sets....156 Definition – the Cartesian product (for n sets)....157 Theorem – the fundamental counting rule....157 Example – bytes....158 Example – colors on computers....159 Counting permutations and combinations of objects....159 Definition – permutation....160 Example – permutations of a simple set....160 Theorem – permutations of a set....160 Example – playlists....161 Growth of factorials....161 Theorem – k-permutations of a set....163 Definition – combination....164 Example – combinations versus permutation for a simple set....164 Theorem – combinations of a set....165 Binomial coefficients....165 Example – teambuilding....166 Example – combinations of balls....167 Applications to memory allocation....168 Example – pre-allocating memory....169 Efficacy of brute-force algorithms....171 Example – Caesar cipher....172 Example – the traveling salesman problem....176 Summary....179 Chapter 5: Elements of Discrete Probability....181 The basics of discrete probability....182 Definition – random experiment....183 Definitions – outcomes, events, and sample spaces....183 Example – tossing coins....184 Example – tossing multiple coins....184 Definition – probability measure....185 Theorem – elementary properties of probability....187 Example – sports....188 Theorem – Monotonicity....189 Theorem – Principle of Inclusion-Exclusion....191 Definition – Laplacian probability....192 Theorem – calculating Laplacian probabilities....192 Example – tossing multiple coins....193 Definition – independent events....194 Example – tossing many coins....195 Conditional probability and Bayes' theorem....197 Definition – conditional probability....198 Example – temperatures and precipitation....198 Theorem – multiplication rules....200 Theorem – the Law of Total Probability....201 Theorem – Bayes' theorem....202 Bayesian spam filtering....203 Random variables, means, and variance....205 Definition – random variable....205 Example – data transfer errors....206 Example – empirical random variable....207 Definition – expectation....208 Example – empirical random variable....208 Definition – variance and standard deviation....209 Theorem – practical calculation of variance....210 Example – empirical random variable....211 Google PageRank I....211 Summary....216 Part II – Implementing Discrete Mathematics in Data and Computer Science....218 Chapter 6: Computational Algorithms in Linear Algebra....219 Understanding linear systems of equations....220 Definition – Linear equations in two variables....221 Definition – The Cartesian coordinate plane....221 Example – A linear equation....222 Definition – System of two linear equations in two variables....224 Definition – Systems of linear equations and their solutions....231 Definition – Consistent, inconsistent, and dependent systems....232 Matrices and matrix representations of linear systems....233 Definition – Matrices and vectors....234 Definition – Matrix addition and subtraction....236 Definition – Scalar multiplication....238 Definition – Transpose of a matrix....239 Definition – Dot product of vectors....241 Definition – Matrix multiplication....241 Example – Multiplying matrices by hand and with NumPy....243 Solving small linear systems with Gaussian elimination....246 Definition – Leading coefficient (pivot)....247 Definition – Reduced row echelon form....248 Algorithm – Gaussian elimination....251 Example – 3-by-3 linear system....252 Solving large linear systems with NumPy....255 Example – A 3-by-3 linear system (with NumPy)....256 Example – Inconsistent and dependent systems with NumPy....257 Example – A 10-by-10 linear system (with NumPy)....259 Summary....261 Chapter 7: Computational Requirements for Algorithms....264 Computational complexity of algorithms....265 Understanding Big-O Notation....272 Complexity of algorithms with fundamental control structures....283 Sequential flow....284 Selection flow....285 Repetitive flow....288 Complexity of common search algorithms....295 Linear search algorithm....295 Binary search algorithm....297 Common classes of computational complexity....302 Summary....305 References....306 Chapter 8: Storage and Feature Extraction of Graphs, Trees, and Networks....307 Understanding graphs, trees, and networks....308 Definition: graph....308 Definition: degree of a vertex....309 Definition: paths....311 Definition: cycles....311 Definition: trees or acyclic graphs....312 Definition: networks....314 Definition: directed graphs....315 Definition: directed networks....316 Definition: adjacent vertices....318 Definition: connected graphs and connected components....319 Using graphs, trees, and networks....321 Storage of graphs and networks....325 Definition: adjacency list....325 Definition: adjacency matrix....326 Definition: adjacency matrix for a directed graph....329 Efficient storage of adjacency data....333 Definition: weight matrix of a network....334 Definition: weight matrix of a directed network....335 Feature extraction of graphs....338 Degrees of vertices in a graph....338 The number of paths between vertices of a specified length....340 Theorem: powers of adjacency matrices....342 Matrix powers in Python....343 Theorem: minimum-edge paths between vi and vj....344 Summary....346 Chapter 9: Searching Data Structures and Finding Shortest Paths....348 Searching Graph and Tree data structures....349 Depth-first search (DFS)....350 A Python implementation of DFS....354 The shortest path problem and variations of the problem....357 Shortest paths on networks....358 Beyond Shortest-Distance Paths....359 Shortest Path Problem Statement....362 Checking whether Solutions Exist....363 Finding Shortest Paths with Brute Force....367 Dijkstra's Algorithm for Finding Shortest Paths....372 Dijkstra's algorithm....373 Applying Dijkstra's Algorithm to a Small Problem....375 Python Implementation of Dijkstra's Algorithm....383 Example – shortest paths....388 Example – A network that is not connected....392 Summary....394 Part III – Real-World Applications of Discrete Mathematics....397 Chapter 10: Regression Analysis with NumPy and Scikit-Learn....398 Dataset....399 Best-fit lines and the least-squares method....403 Variable....403 Linear relationship....404 Regression....404 The line of best fit....406 The least-squares method and the sum of squared errors....410 Least-squares lines with NumPy....413 Least-squares curves with NumPy and SciPy....418 Least-squares surfaces with NumPy and SciPy....422 Summary....426 Chapter 11: Web Searches with PageRank....427 The Development of Search Engines over time....428 Google PageRank II....431 Implementing the PageRank algorithm in Python....442 Applying the Algorithm to Real Data....450 Summary....456 Chapter 12: Principal Component Analysis with Scikit-Learn....458 Understanding eigenvalues, eigenvectors, and orthogonal bases....459 The principal component analysis approach to dimensionality reduction....469 The scikit-learn implementation of PCA....475 An application to real-world data....481 Summary....486 Other Books You May Enjoy....488 Leave a review - let other readers know what you think....490