Practical Discrete Mathematics

Table of contents

1. Practical Discrete Mathematics
2. Why subscribe?
3. Contributors
4. About the authors
5. About the reviewer
6. Packt is searching for authors like you
7. Preface
   1. Who this book is for
   2. What this book covers
      1. Part I – Basic Concepts of Discrete Math
      2. Part II – Implementing Discrete Mathematics in Data and Computer Science
      3. Part III – Real-World Applications of Discrete Mathematics
   3. To get the most out of this book
   4. Download the example code files
   5. Download the color images
   6. Conventions used
   7. Get in touch
   8. Reviews
8. Part I – Basic Concepts of Discrete Math
9. Chapter 1: Key Concepts, Notation, Set Theory, Relations, and Functions
   1. What is discrete mathematics?
   2. Elementary set theory
      1. Definition–Sets and set notation
      2. Definition: Elements of sets
      3. Definition: The empty set
      4. Example: Some examples of sets
      5. Definition: Subsets and supersets
      6. Definition: Set-builder notation
      7. Example: Using set-builder notation
      8. Definition: Basic set operations
      9. Definition: Disjoint sets
      10. Example: Even and odd numbers
      11. Theorem: De Morgan's laws
      12. Example: De Morgan's Law
      13. Definition: Cardinality
      14. Example: Cardinality
   3. Functions and relations
      1. Definition: Relations, domains, and ranges
      2. Definition: Functions
      3. Examples: Relations versus functions
      4. Example: Functions in elementary algebra
      5. Example: Python functions versus mathematical functions
   4. Summary
10. Chapter 2: Formal Logic and Constructing Mathematical Proofs
    1. Formal Logic and Proofs by Truth Tables
       1. Basic Terminology for Formal Logic
       2. Example – an invalid argument
       3. Example – all penguins live in South Africa!
       4. Cores Ideas in Formal Logic
       5. Truth Tables
       6. Example – The Converse
       7. Example – Transitivity Law of Conditional Logic
       8. Example – De Morgan's Laws
       9. Example – The Contrapositive
    2. Direct Mathematical Proofs
       1. Example – Products of Even and Odd Integers
       2. Example – roots of even numbers
       3. Shortcut – The Contrapositive
    3. Proof by Contradiction
       1. Example – is there a smallest positive rational number?
       2. Example – Prove is an Irrational Number
       3. Example – How Many Prime Numbers Are There?
    4. Proof by mathematical induction
       1. Example – Adding 1 + 2 + … + n
       2. Example – Space-Filling Shapes
       3. Example – exponential versus factorial growth
    5. Summary
11. Chapter 3: Computing with Base-n Numbers
    1. Understanding base-n numbers
       1. Example – Decimal numbers
       2. Definition – Base-n numbers
    2. Converting between bases
       1. Converting base-n numbers to decimal numbers
       2. Example – Decimal value of a base-6 number
       3. Base-n to decimal conversion
       4. Example – Decimal to base-2 (binary) conversion
       5. Example – Decimal to binary and hexadecimal conversions in Python
    3. Binary numbers and their applications
       1. Boolean algebra
       2. Example – Netflix users
    4. Hexadecimal numbers and their application
       1. Example – Defining locations in computer memory
       2. Example – Displaying error messages
       3. Example – Media Access Control (MAC) addresses
       4. Example – Defining colors on the web
    5. Summary
12. Chapter 4: Combinatorics Using SciPy
    1. The fundamental counting rule
       1. Definition – the Cartesian product
       2. Theorem – the cardinality of Cartesian products of finite sets
       3. Definition – the Cartesian product (for n sets)
       4. Theorem – the fundamental counting rule
       5. Example – bytes
       6. Example – colors on computers
    2. Counting permutations and combinations of objects
       1. Definition – permutation
       2. Example – permutations of a simple set
       3. Theorem – permutations of a set
       4. Example – playlists
       5. Growth of factorials
       6. Theorem – k-permutations of a set
       7. Definition – combination
       8. Example – combinations versus permutation for a simple set
       9. Theorem – combinations of a set
       10. Binomial coefficients
       11. Example – teambuilding
       12. Example – combinations of balls
    3. Applications to memory allocation
       1. Example – pre-allocating memory
    4. Efficacy of brute-force algorithms
       1. Example – Caesar cipher
       2. Example – the traveling salesman problem
    5. Summary
13. Chapter 5: Elements of Discrete Probability
    1. The basics of discrete probability
       1. Definition – random experiment
       2. Definitions – outcomes, events, and sample spaces
       3. Example – tossing coins
       4. Example – tossing multiple coins
       5. Definition – probability measure
       6. Theorem – elementary properties of probability
       7. Example – sports
       8. Theorem – Monotonicity
       9. Theorem – Principle of Inclusion-Exclusion
       10. Definition – Laplacian probability
       11. Theorem – calculating Laplacian probabilities
       12. Example – tossing multiple coins
       13. Definition – independent events
       14. Example – tossing many coins
    2. Conditional probability and Bayes' theorem
       1. Definition – conditional probability
       2. Example – temperatures and precipitation
       3. Theorem – multiplication rules
       4. Theorem – the Law of Total Probability
       5. Theorem – Bayes' theorem
    3. Bayesian spam filtering
    4. Random variables, means, and variance
       1. Definition – random variable
       2. Example – data transfer errors
       3. Example – empirical random variable
       4. Definition – expectation
       5. Example – empirical random variable
       6. Definition – variance and standard deviation
       7. Theorem – practical calculation of variance
       8. Example – empirical random variable
    5. Google PageRank I
    6. Summary
14. Part II – Implementing Discrete Mathematics in Data and Computer Science
15. Chapter 6: Computational Algorithms in Linear Algebra
    1. Understanding linear systems of equations
       1. Definition – Linear equations in two variables
       2. Definition – The Cartesian coordinate plane
       3. Example – A linear equation
       4. Definition – System of two linear equations in two variables
       5. Definition – Systems of linear equations and their solutions
       6. Definition – Consistent, inconsistent, and dependent systems
    2. Matrices and matrix representations of linear systems
       1. Definition – Matrices and vectors
       2. Definition – Matrix addition and subtraction
       3. Definition – Scalar multiplication
       4. Definition – Transpose of a matrix
       5. Definition – Dot product of vectors
       6. Definition – Matrix multiplication
       7. Example – Multiplying matrices by hand and with NumPy
    3. Solving small linear systems with Gaussian elimination
       1. Definition – Leading coefficient (pivot)
       2. Definition – Reduced row echelon form
       3. Algorithm – Gaussian elimination
       4. Example – 3-by-3 linear system
    4. Solving large linear systems with NumPy
       1. Example – A 3-by-3 linear system (with NumPy)
       2. Example – Inconsistent and dependent systems with NumPy
       3. Example – A 10-by-10 linear system (with NumPy)
    5. Summary
16. Chapter 7: Computational Requirements for Algorithms
    1. Computational complexity of algorithms
    2. Understanding Big-O Notation
    3. Complexity of algorithms with fundamental control structures
       1. Sequential flow
       2. Selection flow
       3. Repetitive flow
    4. Complexity of common search algorithms
       1. Linear search algorithm
       2. Binary search algorithm
    5. Common classes of computational complexity
    6. Summary
    7. References
17. Chapter 8: Storage and Feature Extraction of Graphs, Trees, and Networks
    1. Understanding graphs, trees, and networks
       1. Definition: graph
       2. Definition: degree of a vertex
       3. Definition: paths
       4. Definition: cycles
       5. Definition: trees or acyclic graphs
       6. Definition: networks
       7. Definition: directed graphs
       8. Definition: directed networks
       9. Definition: adjacent vertices
       10. Definition: connected graphs and connected components
    2. Using graphs, trees, and networks
    3. Storage of graphs and networks
       1. Definition: adjacency list
       2. Definition: adjacency matrix
       3. Definition: adjacency matrix for a directed graph
       4. Efficient storage of adjacency data
       5. Definition: weight matrix of a network
       6. Definition: weight matrix of a directed network
    4. Feature extraction of graphs
       1. Degrees of vertices in a graph
       2. The number of paths between vertices of a specified length
       3. Theorem: powers of adjacency matrices
       4. Matrix powers in Python
       5. Theorem: minimum-edge paths between vi and vj
    5. Summary
18. Chapter 9: Searching Data Structures and Finding Shortest Paths
    1. Searching Graph and Tree data structures
    2. Depth-first search (DFS)
       1. A Python implementation of DFS
    3. The shortest path problem and variations of the problem
       1. Shortest paths on networks
       2. Beyond Shortest-Distance Paths
       3. Shortest Path Problem Statement
       4. Checking whether Solutions Exist
    4. Finding Shortest Paths with Brute Force
    5. Dijkstra's Algorithm for Finding Shortest Paths
       1. Dijkstra's algorithm
       2. Applying Dijkstra's Algorithm to a Small Problem
    6. Python Implementation of Dijkstra's Algorithm
       1. Example – shortest paths
       2. Example – A network that is not connected
    7. Summary
19. Part III – Real-World Applications of Discrete Mathematics
20. Chapter 10: Regression Analysis with NumPy and Scikit-Learn
    1. Dataset
    2. Best-fit lines and the least-squares method
       1. Variable
       2. Linear relationship
       3. Regression
       4. The line of best fit
       5. The least-squares method and the sum of squared errors
    3. Least-squares lines with NumPy
    4. Least-squares curves with NumPy and SciPy
    5. Least-squares surfaces with NumPy and SciPy
    6. Summary
21. Chapter 11: Web Searches with PageRank
    1. The Development of Search Engines over time
    2. Google PageRank II
    3. Implementing the PageRank algorithm in Python
    4. Applying the Algorithm to Real Data
    5. Summary
22. Chapter 12: Principal Component Analysis with Scikit-Learn
    1. Understanding eigenvalues, eigenvectors, and orthogonal bases
    2. The principal component analysis approach to dimensionality reduction
    3. The scikit-learn implementation of PCA
    4. An application to real-world data
    5. Summary
23. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think