Discrete Mathematics for Computer Science

Each chapter  begins with motivational content that relates the chapter topic to computer science practice and the book also includes over fifty "Computer Science Connections" which discuss applications to computer science such as Rotation Matrices; Game Trees, Logic, and Winning Tic-Tac(-Toe); Moore's Law; Secret Sharing; The Enigma Machine and the First Computer; Bayesian Modeling and Spam Filtering; and Quantum Computing.

David Liben-Nowell (PhD from MIT) is a Professor and Chair of Computer Science at Carleton College.  His research interests are focused on computational social sciences, particularly the structure and evolution of social networks and computational modeling of spoken-word recognition.

1 On the Point of this Book 101

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 458

4.6 Chapter at a Glance 469

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 818

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

8.5 Chapter at a Glance 850

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 1067

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

12 Index 1201

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.