Connecting Discrete Mathematics and Computer Science

Description

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