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

Cover
Title Page
Copyright and Credits
About Packt
Contributors
Table of Contents
Preface
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
Index