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

Discrete mathematics deals with studying countable, distinct elements, and its principles are widely used in building algorithms for computer science and data science. The knowledge of discrete math concepts will help you understand the algorithms, binary, and general mathematics that sit at the core of data-driven tasks.

Practical Discrete Mathematics is a comprehensive introduction for those who are new to the mathematics of countable objects. This book will help you get up to speed with using discrete math principles to take your computer science skills to a more advanced level.

As you learn the language of discrete mathematics, you'll also cover methods crucial to studying and describing computer science and machine learning objects and algorithms. The chapters that follow will guide you through how memory and CPUs work. In addition to this, you'll understand how to analyze data for useful patterns, before finally exploring how to apply math concepts in network routing, web searching, and data science.

By the end of this book, you'll have a deeper understanding of discrete math and its applications in computer science, and be ready to work on real-world algorithm development and machine learning.

What you will learn

• Understand the terminology and methods in discrete math and their usage in algorithms and data problems
• Use Boolean algebra in formal logic and elementary control structures
• Implement combinatorics to measure computational complexity and manage memory allocation
• Use random variables, calculate descriptive statistics, and find average-case computational complexity
• Solve graph problems involved in routing, pathfinding, and graph searches, such as depth-first search
• Perform ML tasks such as data visualization, regression, and dimensionality reduction

Who this book is for

This book is for computer scientists looking to expand their knowledge of discrete math, the core topic of their field. University students looking to get hands-on with computer science, mathematics, statistics, engineering, or related disciplines will also find this book useful. Basic Python programming skills and knowledge of elementary real-number algebra are required to get started with this book.