Cover image for Practical Discrete Mathematics

Practical Discrete Mathematics

Release Date: 2021/02/01
ISBN: 9781838983147
Topic:
0%
20
Chapters
0-1
Hours read
0k
Total Words
    Start Reading Now    
       Add to Wishlist       
View table of contents

A practical guide simplifying discrete math for curious minds and demonstrating its application in solving problems related to software development, computer algorithms, and data science

Key Features

  • Apply the math of countable objects to practical problems in computer science
  • Explore modern Python libraries such as scikit-learn, NumPy, and SciPy for performing mathematics
  • Learn complex statistical and mathematical concepts with the help of hands-on examples and expert guidance

Book Description

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.

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