book

Practical Discrete Mathematics

by Ryan T. White, Archana Tikayat Ray

February 2021

Intermediate to advanced

330 pages

7h 11m

English

Packt Publishing

Read now

Unlock full access

Why subscribe?ContributorsAbout the authorsAbout the reviewerPackt is searching for authors like you
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
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
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
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
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
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
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

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
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
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
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
The Development of Search Engines over timeGoogle PageRank IIImplementing the PageRank algorithm in PythonApplying the Algorithm to Real DataSummary
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
Leave a review - let other readers know what you think

Content preview from Practical Discrete Mathematics

Preface

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 another level. You'll learn the language of discrete mathematics and methods crucial to studying and describing objects and algorithms from computer science and machine learning. Complete with real-world examples, this book covers the internal workings of memory and CPUs, analyzes data for useful patterns, and shows you how to solve problems in network routing, web searching, and data science.

Who this book is for

This book is for computer scientists looking to expand their knowledge of the core ...

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.

Start your free trial

Practical Linear Algebra for Data Science

Publisher Resources

ISBN: 9781838983147Supplemental Content

Practical Discrete Mathematics

by Ryan T. White, Archana Tikayat Ray

Preface

Who this book is for

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.

You might also like

Practical Linear Algebra for Data Science

Advanced Engineering Mathematics, 7th Edition

Probability and Statistics for Computer Scientists, 2nd Edition

Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

Publisher Resources

Preface

Who this book is for

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.

You might also like

Practical Linear Algebra for Data Science

Advanced Engineering Mathematics, 7th Edition

Probability and Statistics for Computer Scientists, 2nd Edition

Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

Publisher Resources

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.