Discrete Mathematics for Computer Science
September 2017, ©2018
Written exclusively with computer science students in mind, Discrete Mathematics for Computer Science provides a comprehensive treatment of standard course topics for the introductory discrete mathematics course with a strong emphasis on the relationship between the concepts and their application to computer science. The book has been crafted to enhance teaching and learning ease and includes a wide selection of exercises, detailed exploration problems, examples and problems inspired by wide-ranging applications of computer science and handy quick reference guides for key technical topics throughout. Discrete Mathematics for Computer Science provides a lucidly written introduction to discrete mathematics with abundant support for learning, including over 450 examples, thorough chapter summaries, simple quizzes, and approximately 1600 homework exercises of widely varying difficulty.
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.
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
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.
- Wiley E-Texts are powered by VitalSource and accessed via the VitalSource Bookshelf reader, available online and via a downloadable app.
- Wiley E-Texts are accessible online and offline, and can be read on a variety of devices, including smartphones and tablets.
- Wiley E-Texts are non-returnable and non-refundable.
- Wiley E-Texts are protected by DRM. For specific DRM policies, please refer to our FAQ.
- WileyPLUS registration codes are NOT included with any Wiley E-Text. For informationon WileyPLUS, click here .
- To learn more about Wiley E-Texts, please refer to our FAQ.
- E-books are offered as e-Pubs or PDFs. To download and read them, users must install Adobe Digital Editions (ADE) on their PC.
- E-books have DRM protection on them, which means only the person who purchases and downloads the e-book can access it.
- E-books are non-returnable and non-refundable.
- To learn more about our e-books, please refer to our FAQ.