Fundamentals of Discrete Math for Computer Science
Preface
Acknowledgments
Contents
1: Algorithms, Numbers, and Machines
1.1 What Is an Algorithm?
1.2 Integer Algorithms and Complexity
1.2.1 Prime Testing
1.2.2 Real Numbers
1.2.3 More Prime Testing
1.2.4 Prime Factorization
1.2.5 Logarithms
1.2.6 Greatest Common Divisor
1.3 Machine Representation of Numbers
1.3.1 Approximation Errors
1.3.2 Base 2, 8, and 16
1.4 Numerical Solutions
1.4.1 NewtonΒ΄s Method for Square Roots
1.4.2 The Bisection Algorithm
2: Sets, Sequences, and Counting
2.1 NaΓ―ve Set Theory
2.1.1 The Diabolical Librarian
2.1.2 Operations on Sets and Cardinality
2.1.3 The Pigeonhole Principle
2.2 Sequences
2.2.1 The Characteristic Sequence of a Subset
2.3 Counting
2.3.1 Number of k-Sequences on an n-Set
2.3.2 Number of Subsets of an n-Set
2.3.3 Number of k-Permutations on an n-Set
2.3.4 n-Factorial
2.3.5 Number of k-Subsets of an n-Set
2.3.6 PascalΒ΄s Triangle
2.3.7 Counting Algorithmically (Without a Formula)
2.4 Infinite Sequences and Complexity Functions
2.4.1 The Towers of Hanoi
2.4.2 Bad Complexity Functions
3: Boolean Expressions, Logic, and Proof
3.1 The Greedy Algorithm and Three Cookie Problems
3.1.1 The Greedy Algorithm
3.2 Boolean Expressions and Truth Tables
3.2.1 The Negation Operator
3.2.2 The Conjunction Operator
3.2.3 The Disjunction Operator
3.2.4 The Conditional Operator
3.2.5 The Biconditional Operator
3.3 Predicates and Quantifiers
3.4 Valid Arguments
3.5 Examples of Proofs
3.5.1 Direct Proof
3.5.2 Indirect Proof
3.5.3 CantorΒ΄s Diagonalization Process
3.6 Mathematical Induction
3.6.1 Strong Induction
3.7 Proofs Promised in Chap. 1
3.7.1 Russian Peasant Multiplication Is Correct
3.7.2 Resolving the Cake Cutting Conundrum
3.7.3 Casting Out Nines
3.7.4 EuclidΒ΄s Algorithm for GCD Is Correct
3.8 The Proof Promised in Chap. 2
4: Searching and Sorting
4.1 Searching
4.1.1 Searching an Arbitrary List
4.1.2 Searching a Sorted List
4.2 Branching Diagrams
4.2.1 A Second Version of Binary Search
4.3 Sorting
4.3.1 Selection Sorts
4.3.2 Exchange Sorts
4.4 Binary Trees with (at Least) n! Leaves
4.5 Partition Sorts
4.6 Comparison of Sorting Algorithms
4.6.1 Timings and Operation Counts
5: Graphs and Trees
5.1 Introduction
5.1.1 Degrees
5.1.2 Eulerian Graphs
5.1.3 Hamiltonian Graphs
5.2 Paths, Circuits, and Polygons
5.2.1 Subgraphs Determined by Paths
5.3 Trees
5.3.1 Traversals
5.4 Edge-Weighted Graphs
5.4.1 Shortest Paths
5.5 Directed Graphs
5.5.1 Dipaths
5.5.2 Distance Function
5.5.3 DijkstraΒ΄s Algorithm
5.5.4 Floyd-Warshall Algorithm
6: Relations: Especially on (Integer) Sequences
6.1 Relations and Representations
6.1.1 Matrix Representation
6.1.2 Directed Graph Representation
6.1.3 Properties of Relations
6.2 Equivalence Relations
6.2.1 Matrix and Digraph of an Equivalence Relation
6.3 Order Relations
6.3.1 Matrix and Digraph of a Partial Order
6.3.2 Minimal and Maximal Elements
6.4 Relations on Finite Sequences
6.4.1 Domination
6.4.2 Lexicographic Order
6.5 Relations on Infinite Sequences
6.5.1 Asymptotic Dominance and Big-Oh Notation
6.5.2 Asymptotic Equivalence and Big-Theta Notation
6.5.2.1 Polynomials
6.5.3 Asymptotic Ranking
6.5.4 Strong Asymptotic Dominance and Little-Oh Notation
7: Sequences and Series
7.1 Examples Defined by Recurrence Equations
7.2 Solving First-Order Linear Recurrence Equations
7.3 The Fibonacci Sequence
7.3.1 Algorithms for the Fibonacci Sequence
7.3.2 The Golden Ratio
7.3.3 The Fibonacci Sequence and the Golden Ratio
7.3.4 The Order of the Fibonacci Sequence
7.3.5 The Complexity of EuclidΒ΄s Algorithm for GCD
7.4 Solving Second-Order Linear Recurrence Equations
7.5 Infinite Series
7.5.1 ZenoΒ΄s Paradoxes
7.5.2 Formal Definitions of Convergence of Sequences and Series
8: Generating Sequences and Subsets
8.1 Generating Sequences in Lexicographic-Order
8.2 Generating All k-Sequences on {1..n}
8.2.1 Average-Case Complexity
8.3 Generating Subsets of {1..n} as Increasing Sequences
8.4 Generating Permutations in Lexicographic-Order
8.4.1 Generating All k-Permutations of {1..n} in Lex-Order
9: Discrete Probability and Average-Case Complexity
9.1 Probabilistic Models
9.1.1 Sample Spaces
9.1.2 Probability Functions
9.1.3 The Special Case of Equally Likely Outcomes
9.2 Conditional Probability
9.2.1 Combinations of Events
9.2.2 Conditional Probability
9.2.3 Independent Events
9.2.4 Mutually Exclusive Events
9.3 Random Variables and Expected Values
9.3.1 Expected Frequency
9.3.2 Expected Values
9.3.3 Probability Distributions
9.4 Standard Distributions and Their Expected Values
9.4.1 The Uniform Distribution
9.4.2 The Binomial Distribution
9.4.3 The Geometric Distribution
9.5 Conditional Expected Values
9.5.1 Conditional Expectation
9.6 Average-Case Complexity
9.6.1 Applying Expectation to Linear Search
9.6.2 Applying Expectation to QuickSort
10: Turing Machines
10.1 What Is an Algorithm?
10.1.1 The Church-Turing Thesis
10.1.2 Universal Turing Machine: As a Computational Model
10.1.3 The Halting Problem
Index