Title Details

2 Basic Data Types 201

2.1 Why You Might Care 202

2.2 Booleans, Numbers, and Arithmetic 203

2.3 Sets: Unordered Collections 222

2.4 Sequences, Vectors, and Matrices: Ordered Collections 237

2.5 Functions 253

2.6 Chapter at a Glance 270

3 Logic 301

3.1 Why You Might Care 302

3.2 An Introduction to Propositional Logic 303

3.3 Propositional Logic: Some Extensions 317

3.4 An Introduction to Predicate Logic 331

3.5 Predicate Logic: Nested Quantifiers 349

3.6 Chapter at a Glance 362

4 Proofs 401

4.1 Why You Might Care 402

4.2 Error-Correcting Codes 403

4.3 Proofs and Proof Techniques 423

4.4 Some Examples of Proofs 441

4.5 Common Errors in Proofs 457

4.6 Chapter at a Glance 468

5 Mathematical Induction 501

5.1 Why You Might Care 502

5.2 Proofs by Mathematical Induction 503

5.3 Strong Induction 521

5.4 Recursively Defined Structures and Structural Induction 533

5.5 Chapter at a Glance 546

6 Analysis of Algorithms 601

6.1 Why You Might Care 602

6.2 Asymptotics 603

6.3 Asymptotic Analysis of Algorithms 617

6.4 Recurrence Relations: Analyzing Recursive Algorithms 631

6.5 Recurrence Relations: The Master Method 647

6.6 Chapter at a Glance 657

7 Number Theory 701

7.1 Why You Might Care 702

7.2 Modular Arithmetic 703

7.3 Primality and Relative Primality 717

7.4 Multiplicative Inverses 734

7.5 Cryptography 745

7.6 Chapter at a Glance 756

8 Relations 801

8.1 Why You Might Care 802

8.2 Formal Introduction 803

8.3 Properties of Relations: Reflexivity, Symmetry, and Transitivity 817

8.4 Special Relations: Equivalence Relations and Partial/Total Orders 832

8.5 Chapter at a Glance 848

9 Counting 901

9.1 Why You Might Care 902

9.2 Counting Unions and Sequences 903

9.3 Using Functions to Count 926

9.4 Combinations and Permutations 944

9.5 Chapter at a Glance 965

10 Probability 1001

10.1 Why You Might Care 1002

10.2 Probability, Outcomes, and Events 1005

10.3 Independence and Conditional Probability 1021

10.4 Random Variables and Expectation 1041

10.5 Chapter at a Glance 1066

11 Graphs and Trees 1101

11.1 Why You Might Care 1102

11.2 Formal Introduction 1103

11.3 Paths, Connectivity, and Distances 1129

11.4 Trees 1147

11.5 Weighted Graphs 1164

11.6 Chapter at a Glance 1177

Random Walks and Ranking Web Pages 1174