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

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: