Connecting Discrete Mathematics and Computer Science

✍ Scribed by David Liben-Nowell

• Publisher: Cambridge University Press
• Year: 2022
• Tongue: English
• Leaves: 694
• Category: Library

✦ Table of Contents

Cover
Half-title Page
Reviews
Title Page
Copyright Page
Dedication
Contents
List of Computer Science Connections
Acknowledgments
Credits
1 On the Point of this Book
2 Basic Data Types
2.1 Why You Might Care
2.2 Booleans, Numbers, and Arithmetic
2.3 Sets: Unordered Collections
2.4 Sequences, Vectors, and Matrices: Ordered Collections
2.5 Functions
2.6 Chapter at a Glance
3 Logic
3.1 Why You Might Care
3.2 An Introduction to Propositional Logic
3.3 Propositional Logic: Some Extensions
3.4 An Introduction to Predicate Logic
3.5 Predicate Logic: Nested Quantifiers
3.6 Chapter at a Glance
4 Proofs
4.1 Why You Might Care
4.2 Error-Correcting Codes
4.3 Proofs and Proof Techniques
4.4 Some Examples of Proofs
4.5 Common Errors in Proofs
4.6 Chapter at a Glance
5 Mathematical Induction
5.1 Why You Might Care
5.2 Proofs by Mathematical Induction
5.3 Strong Induction
5.4 Recursively Defined Structures and Structural Induction
5.5 Chapter at a Glance
6 Analysis of Algorithms
6.1 Why You Might Care
6.2 Asymptotics
6.3 Asymptotic Analysis of Algorithms
6.4 Recurrence Relations: Analyzing Recursive Algorithms
6.5 An Extension: Recurrence Relations of the Form T(n)=aT([frac(n)(b)])+cn[sup(k)]
6.6 Chapter at a Glance
7 Number Theory
7.1 Why You Might Care
7.2 Modular Arithmetic
7.3 Primality and Relative Primality
7.4 Multiplicative Inverses
7.5 Cryptography
7.6 Chapter at a Glance
8 Relations
8.1 Why You Might Care
8.2 Formal Introduction
8.3 Properties of Relations: Reflexivity, Symmetry, and Transitivity
8.4 Special Relations: Equivalence Relations and Partial/Total Orders
8.5 Chapter at a Glance
9 Counting
9.1 Why You Might Care
9.2 Counting Unions and Sequences
9.3 Using Functions to Count
9.4 Combinations and Permutations
9.5 Chapter at a Glance
10 Probability
10.1 Why You Might Care
10.2 Probability, Outcomes, and Events
10.3 Independence and Conditional Probability
10.4 Random Variables and Expectation
10.5 Chapter at a Glance
11 Graphs and Trees
11.1 Why You Might Care
11.2 Formal Introduction
11.3 Paths, Connectivity, and Distances
11.4 Trees
11.5 Weighted Graphs
11.6 Chapter at a Glance
12 Looking Forward
References
Index