Practical Discrete Mathematics by Ryan T. White -- Read -- Imperial Library of Trantor

Index

Practical Discrete Mathematics Why subscribe? Contributors About the authors About the reviewer Packt is searching for authors like you Preface

Who this book is for What this book covers

Part I – Basic Concepts of Discrete Math Part II – Implementing Discrete Mathematics in Data and Computer Science Part III – Real-World Applications of Discrete Mathematics

To get the most out of this book Download the example code files Download the color images Conventions used Get in touch Reviews

Part I – Basic Concepts of Discrete Math Chapter 1: Key Concepts, Notation, Set Theory, Relations, and Functions

What is discrete mathematics? Elementary set theory

Definition–Sets and set notation Definition: Elements of sets Definition: The empty set Example: Some examples of sets Definition: Subsets and supersets Definition: Set-builder notation Example: Using set-builder notation Definition: Basic set operations Definition: Disjoint sets Example: Even and odd numbers Theorem: De Morgan's laws Example: De Morgan's Law Definition: Cardinality Example: Cardinality

Functions and relations

Definition: Relations, domains, and ranges Definition: Functions Examples: Relations versus functions Example: Functions in elementary algebra Example: Python functions versus mathematical functions

Summary

Chapter 2: Formal Logic and Constructing Mathematical Proofs

Formal Logic and Proofs by Truth Tables

Basic Terminology for Formal Logic Example – an invalid argument Example – all penguins live in South Africa! Cores Ideas in Formal Logic Truth Tables Example – The Converse Example – Transitivity Law of Conditional Logic Example – De Morgan's Laws Example – The Contrapositive

Direct Mathematical Proofs

Example – Products of Even and Odd Integers Example – roots of even numbers Shortcut – The Contrapositive

Proof by Contradiction

Example – is there a smallest positive rational number? Example – Prove is an Irrational Number Example – How Many Prime Numbers Are There?

Proof by mathematical induction

Example – Adding 1 + 2 + … + n Example – Space-Filling Shapes Example – exponential versus factorial growth

Summary

Chapter 3: Computing with Base-n Numbers

Understanding base-n numbers

Example – Decimal numbers Definition – Base-n numbers

Converting between bases

Converting base-n numbers to decimal numbers Example – Decimal value of a base-6 number Base-n to decimal conversion Example – Decimal to base-2 (binary) conversion Example – Decimal to binary and hexadecimal conversions in Python

Binary numbers and their applications

Boolean algebra Example – Netflix users

Hexadecimal numbers and their application

Example – Defining locations in computer memory Example – Displaying error messages Example – Media Access Control (MAC) addresses Example – Defining colors on the web

Summary

Chapter 4: Combinatorics Using SciPy

The fundamental counting rule

Definition – the Cartesian product Theorem – the cardinality of Cartesian products of finite sets Definition – the Cartesian product (for n sets) Theorem – the fundamental counting rule Example – bytes Example – colors on computers

Counting permutations and combinations of objects

Definition – permutation Example – permutations of a simple set Theorem – permutations of a set Example – playlists Growth of factorials Theorem – k-permutations of a set Definition – combination Example – combinations versus permutation for a simple set Theorem – combinations of a set Binomial coefficients Example – teambuilding Example – combinations of balls

Applications to memory allocation

Example – pre-allocating memory

Efficacy of brute-force algorithms

Example – Caesar cipher Example – the traveling salesman problem

Summary

Chapter 5: Elements of Discrete Probability

The basics of discrete probability

Definition – random experiment Definitions – outcomes, events, and sample spaces Example – tossing coins Example – tossing multiple coins Definition – probability measure Theorem – elementary properties of probability Example – sports Theorem – Monotonicity Theorem – Principle of Inclusion-Exclusion Definition – Laplacian probability Theorem – calculating Laplacian probabilities Example – tossing multiple coins Definition – independent events Example – tossing many coins

Conditional probability and Bayes' theorem

Definition – conditional probability Example – temperatures and precipitation Theorem – multiplication rules Theorem – the Law of Total Probability Theorem – Bayes' theorem

Bayesian spam filtering Random variables, means, and variance

Definition – random variable Example – data transfer errors Example – empirical random variable Definition – expectation Example – empirical random variable Definition – variance and standard deviation Theorem – practical calculation of variance Example – empirical random variable

Google PageRank I Summary

Part II – Implementing Discrete Mathematics in Data and Computer Science Chapter 6: Computational Algorithms in Linear Algebra

Understanding linear systems of equations

Definition – Linear equations in two variables Definition – The Cartesian coordinate plane Example – A linear equation Definition – System of two linear equations in two variables Definition – Systems of linear equations and their solutions Definition – Consistent, inconsistent, and dependent systems

Matrices and matrix representations of linear systems

Definition – Matrices and vectors Definition – Matrix addition and subtraction Definition – Scalar multiplication Definition – Transpose of a matrix Definition – Dot product of vectors Definition – Matrix multiplication Example – Multiplying matrices by hand and with NumPy

Solving small linear systems with Gaussian elimination

Definition – Leading coefficient (pivot) Definition – Reduced row echelon form Algorithm – Gaussian elimination Example – 3-by-3 linear system

Solving large linear systems with NumPy

Example – A 3-by-3 linear system (with NumPy) Example – Inconsistent and dependent systems with NumPy Example – A 10-by-10 linear system (with NumPy)

Summary

Chapter 7: Computational Requirements for Algorithms

Computational complexity of algorithms Understanding Big-O Notation Complexity of algorithms with fundamental control structures

Sequential flow Selection flow Repetitive flow

Complexity of common search algorithms

Linear search algorithm Binary search algorithm

Common classes of computational complexity Summary References

Chapter 8: Storage and Feature Extraction of Graphs, Trees, and Networks

Understanding graphs, trees, and networks

Definition: graph Definition: degree of a vertex Definition: paths Definition: cycles Definition: trees or acyclic graphs Definition: networks Definition: directed graphs Definition: directed networks Definition: adjacent vertices Definition: connected graphs and connected components

Using graphs, trees, and networks Storage of graphs and networks

Definition: adjacency list Definition: adjacency matrix Definition: adjacency matrix for a directed graph Efficient storage of adjacency data Definition: weight matrix of a network Definition: weight matrix of a directed network

Feature extraction of graphs

Degrees of vertices in a graph The number of paths between vertices of a specified length Theorem: powers of adjacency matrices Matrix powers in Python Theorem: minimum-edge paths between vi and vj

Summary

Chapter 9: Searching Data Structures and Finding Shortest Paths

Searching Graph and Tree data structures Depth-first search (DFS)

A Python implementation of DFS

The shortest path problem and variations of the problem

Shortest paths on networks Beyond Shortest-Distance Paths Shortest Path Problem Statement Checking whether Solutions Exist

Finding Shortest Paths with Brute Force Dijkstra's Algorithm for Finding Shortest Paths

Dijkstra's algorithm Applying Dijkstra's Algorithm to a Small Problem

Python Implementation of Dijkstra's Algorithm

Example – shortest paths Example – A network that is not connected

Summary

Part III – Real-World Applications of Discrete Mathematics Chapter 10: Regression Analysis with NumPy and Scikit-Learn

Dataset Best-fit lines and the least-squares method

Variable Linear relationship Regression The line of best fit The least-squares method and the sum of squared errors

Least-squares lines with NumPy Least-squares curves with NumPy and SciPy Least-squares surfaces with NumPy and SciPy Summary

Chapter 11: Web Searches with PageRank

The Development of Search Engines over time Google PageRank II Implementing the PageRank algorithm in Python Applying the Algorithm to Real Data Summary

Chapter 12: Principal Component Analysis with Scikit-Learn

Understanding eigenvalues, eigenvectors, and orthogonal bases The principal component analysis approach to dimensionality reduction The scikit-learn implementation of PCA An application to real-world data Summary

Other Books You May Enjoy

Leave a review - let other readers know what you think

← Prev
Back
Next →

← Prev
Back
Next →