book

Practical Discrete Mathematics

Name: Practical Discrete Mathematics
ISBN: 9781838983147

by Ryan T. White, Archana Tikayat Ray

February 2021

Intermediate to advanced

330 pages

7h 11m

English

Packt Publishing

Read now

Unlock full access

Practical Discrete Mathematics
Why subscribe?ContributorsAbout the authorsAbout the reviewerPackt is searching for authors like you
Preface
Who this book is forWhat this book coversPart I – Basic Concepts of Discrete MathPart II – Implementing Discrete Mathematics in Data and Computer SciencePart III – Real-World Applications of Discrete MathematicsTo get the most out of this bookDownload the example code filesDownload the color imagesConventions usedGet in touchReviews
Part I – Basic Concepts of Discrete Math
Chapter 1: Key Concepts, Notation, Set Theory, Relations, and Functions
What is discrete mathematics?Elementary set theoryDefinition–Sets and set notationDefinition: Elements of sets Definition: The empty set Example: Some examples of sets Definition: Subsets and supersetsDefinition: Set-builder notationExample: Using set-builder notationDefinition: Basic set operationsDefinition: Disjoint setsExample: Even and odd numbersTheorem: De Morgan's lawsExample: De Morgan's LawDefinition: CardinalityExample: CardinalityFunctions and relationsDefinition: Relations, domains, and rangesDefinition: FunctionsExamples: Relations versus functionsExample: Functions in elementary algebraExample: Python functions versus mathematical functions Summary
Chapter 2: Formal Logic and Constructing Mathematical Proofs
Formal Logic and Proofs by Truth TablesBasic Terminology for Formal LogicExample – an invalid argumentExample – all penguins live in South Africa!Cores Ideas in Formal LogicTruth TablesExample – The ConverseExample – Transitivity Law of Conditional LogicExample – De Morgan's LawsExample – The ContrapositiveDirect Mathematical ProofsExample – Products of Even and Odd IntegersExample – roots of even numbersShortcut – The ContrapositiveProof by ContradictionExample – is there a smallest positive rational number?Example – Prove is an Irrational NumberExample – How Many Prime Numbers Are There?Proof by mathematical inductionExample – Adding 1 + 2 + … + nExample – Space-Filling ShapesExample – exponential versus factorial growthSummary
Chapter 3: Computing with Base-n Numbers
Understanding base-n numbers Example – Decimal numbersDefinition – Base-n numbersConverting between basesConverting base-n numbers to decimal numbersExample – Decimal value of a base-6 numberBase-n to decimal conversion Example – Decimal to base-2 (binary) conversion Example – Decimal to binary and hexadecimal conversions in PythonBinary numbers and their applications Boolean algebra Example – Netflix usersHexadecimal numbers and their applicationExample – Defining locations in computer memoryExample – Displaying error messagesExample – Media Access Control (MAC) addressesExample – Defining colors on the webSummary
Chapter 4: Combinatorics Using SciPy
The fundamental counting ruleDefinition – the Cartesian productTheorem – the cardinality of Cartesian products of finite setsDefinition – the Cartesian product (for n sets)Theorem – the fundamental counting ruleExample – bytesExample – colors on computersCounting permutations and combinations of objectsDefinition – permutationExample – permutations of a simple setTheorem – permutations of a setExample – playlistsGrowth of factorialsTheorem – k-permutations of a setDefinition – combinationExample – combinations versus permutation for a simple setTheorem – combinations of a setBinomial coefficientsExample – teambuildingExample – combinations of ballsApplications to memory allocationExample – pre-allocating memoryEfficacy of brute-force algorithmsExample – Caesar cipherExample – the traveling salesman problemSummary
Chapter 5: Elements of Discrete Probability
The basics of discrete probabilityDefinition – random experimentDefinitions – outcomes, events, and sample spacesExample – tossing coinsExample – tossing multiple coinsDefinition – probability measureTheorem – elementary properties of probabilityExample – sportsTheorem – MonotonicityTheorem – Principle of Inclusion-ExclusionDefinition – Laplacian probabilityTheorem – calculating Laplacian probabilitiesExample – tossing multiple coinsDefinition – independent eventsExample – tossing many coinsConditional probability and Bayes' theoremDefinition – conditional probabilityExample – temperatures and precipitationTheorem – multiplication rulesTheorem – the Law of Total ProbabilityTheorem – Bayes' theoremBayesian spam filteringRandom variables, means, and varianceDefinition – random variableExample – data transfer errorsExample – empirical random variableDefinition – expectationExample – empirical random variableDefinition – variance and standard deviationTheorem – practical calculation of varianceExample – empirical random variableGoogle PageRank ISummary
Part II – Implementing Discrete Mathematics in Data and Computer Science
Chapter 6: Computational Algorithms in Linear Algebra
Understanding linear systems of equationsDefinition – Linear equations in two variablesDefinition – The Cartesian coordinate planeExample – A linear equationDefinition – System of two linear equations in two variablesDefinition – Systems of linear equations and their solutionsDefinition – Consistent, inconsistent, and dependent systemsMatrices and matrix representations of linear systemsDefinition – Matrices and vectorsDefinition – Matrix addition and subtractionDefinition – Scalar multiplicationDefinition – Transpose of a matrixDefinition – Dot product of vectorsDefinition – Matrix multiplicationExample – Multiplying matrices by hand and with NumPySolving small linear systems with Gaussian eliminationDefinition – Leading coefficient (pivot)Definition – Reduced row echelon formAlgorithm – Gaussian eliminationExample – 3-by-3 linear systemSolving large linear systems with NumPyExample – A 3-by-3 linear system (with NumPy)Example – Inconsistent and dependent systems with NumPyExample – A 10-by-10 linear system (with NumPy)Summary

Chapter 7: Computational Requirements for Algorithms
Computational complexity of algorithms Understanding Big-O NotationComplexity of algorithms with fundamental control structures Sequential flowSelection flowRepetitive flowComplexity 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 networksDefinition: graphDefinition: degree of a vertexDefinition: pathsDefinition: cyclesDefinition: trees or acyclic graphsDefinition: networksDefinition: directed graphsDefinition: directed networksDefinition: adjacent verticesDefinition: connected graphs and connected componentsUsing graphs, trees, and networksStorage of graphs and networksDefinition: adjacency listDefinition: adjacency matrixDefinition: adjacency matrix for a directed graphEfficient storage of adjacency dataDefinition: weight matrix of a networkDefinition: weight matrix of a directed networkFeature extraction of graphsDegrees of vertices in a graphThe number of paths between vertices of a specified lengthTheorem: powers of adjacency matrices Matrix powers in PythonTheorem: minimum-edge paths between vi and vjSummary
Chapter 9: Searching Data Structures and Finding Shortest Paths
Searching Graph and Tree data structuresDepth-first search (DFS)A Python implementation of DFSThe shortest path problem and variations of the problemShortest paths on networksBeyond Shortest-Distance PathsShortest Path Problem StatementChecking whether Solutions ExistFinding Shortest Paths with Brute ForceDijkstra's Algorithm for Finding Shortest PathsDijkstra's algorithmApplying Dijkstra's Algorithm to a Small ProblemPython Implementation of Dijkstra's AlgorithmExample – shortest pathsExample – A network that is not connectedSummary
Part III – Real-World Applications of Discrete Mathematics
Chapter 10: Regression Analysis with NumPy and Scikit-Learn
DatasetBest-fit lines and the least-squares method Variable Linear relationship RegressionThe line of best fit The least-squares method and the sum of squared errorsLeast-squares lines with NumPyLeast-squares curves with NumPy and SciPyLeast-squares surfaces with NumPy and SciPySummary
Chapter 11: Web Searches with PageRank
The Development of Search Engines over timeGoogle PageRank IIImplementing the PageRank algorithm in PythonApplying the Algorithm to Real DataSummary
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

Content preview from Practical Discrete Mathematics

Chapter 9: Searching Data Structures and Finding Shortest Paths

This chapter will discuss the searching techniques of graph, tree, and network data structures and practical applications of graph searches. We will introduce and analyze two popular algorithms for related problems: depth-first search (DFS) for graph searches and Dijkstra's algorithm for finding the shortest paths between vertices in networks. Both are introduced on small graphs to build intuitive understanding, and Python implementations are written that can scale up to real-world problems.

In this chapter, we will cover the following topics:

Searching graph and tree data structures
Depth-first search algorithm
The shortest path problem and variations of the problem
Finding ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781838983147

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Practical Discrete Mathematics

by Ryan T. White, Archana Tikayat Ray

Chapter 9: Searching Data Structures and Finding Shortest Paths

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.