Computer science majors taking a non-programming-based course like discrete mathematics might ask 'Why do I need to learn this?' Written with these students in mind, this text introduces the mathematical foundations of computer science by providing a comprehensive treatment of standard technical topics while simultaneously illustrating some of the broad-ranging applications of that material throughout the field. Chapters on core topics from discrete structures – like logic, proofs, number theory, counting, probability, graphs – are augmented with around 60 'computer science connections' pages introducing their applications: for example, game trees (logic), triangulation of scenes in computer graphics (induction), the Enigma machine (counting), algorithmic bias (relations), differential privacy (probability), and paired kidney transplants (graphs). Pedagogical features include 'Why You Might Care' sections, quick-reference chapter guides and key terms and results summaries, problem-solving and writing tips, 'Taking it Further' asides with more technical details, and around 1700 exercises, 435 worked examples, and 480 figures.

nexusstc/Connecting Discrete Mathematics and Computer Science/a93b5221c0a27adf59486947e3c8152f.pdf

lgli/Connecting Discrete Mathematics and Computer Science.pdf

lgrsnf/Connecting Discrete Mathematics and Computer Science.pdf

zlib/Computers/Computer Science/Liben-Nowell, David/Connecting Discrete Mathematics and Computer Science, 2nd Edition_27110411.pdf

Connecting Discrete Mathematics and Computer Science (Law in Context)

CONNECTING DISCRETE MATHEMATICS AND COMPUTER SCIENCE : volume 2

David Liben-Nowell

Cambridge, UK

Second edition, Cambridge, United Kingdom, 2022

United Kingdom and Ireland, United Kingdom

Second editión, London [etc, 2022

2, PS, 2022

2, 2023

uuuu

Publisher's PDF

producers:
Cambridge University Press; modified using iText® 5.5.13 ©2000-2018 iText Group NV (AGPL-version)

{"edition":"2","isbns":["1009150480","1009150499","9781009150484","9781009150491"],"last_page":694,"publisher":"Cambridge, UK"}

Cover 1
Half-title Page 3
Reviews 4
Title Page 5
Copyright Page 6
Dedication 7
Contents 9
List of Computer Science Connections 13
Acknowledgments 15
Credits 17
1 On the Point of this Book 19
2 Basic Data Types 23
2.1 Why You Might Care 24
2.2 Booleans, Numbers, and Arithmetic 25
2.3 Sets: Unordered Collections 44
2.4 Sequences, Vectors, and Matrices: Ordered Collections 60
2.5 Functions 77
2.6 Chapter at a Glance 93
3 Logic 97
3.1 Why You Might Care 98
3.2 An Introduction to Propositional Logic 99
3.3 Propositional Logic: Some Extensions 113
3.4 An Introduction to Predicate Logic 127
3.5 Predicate Logic: Nested Quantifiers 145
3.6 Chapter at a Glance 158
4 Proofs 161
4.1 Why You Might Care 162
4.2 Error-Correcting Codes 163
4.3 Proofs and Proof Techniques 184
4.4 Some Examples of Proofs 202
4.5 Common Errors in Proofs 219
4.6 Chapter at a Glance 230
5 Mathematical Induction 233
5.1 Why You Might Care 234
5.2 Proofs by Mathematical Induction 235
5.3 Strong Induction 255
5.4 Recursively Defined Structures and Structural Induction 268
5.5 Chapter at a Glance 281
6 Analysis of Algorithms 285
6.1 Why You Might Care 286
6.2 Asymptotics 287
6.3 Asymptotic Analysis of Algorithms 301
6.4 Recurrence Relations: Analyzing Recursive Algorithms 316
6.5 An Extension: Recurrence Relations of the Form T(n)=aT([frac(n)(b)])+cn[sup(k)] 332
6.6 Chapter at a Glance 341
7 Number Theory 345
7.1 Why You Might Care 346
7.2 Modular Arithmetic 347
7.3 Primality and Relative Primality 361
7.4 Multiplicative Inverses 378
7.5 Cryptography 389
7.6 Chapter at a Glance 400
8 Relations 403
8.1 Why You Might Care 404
8.2 Formal Introduction 405
8.3 Properties of Relations: Reflexivity, Symmetry, and Transitivity 420
8.4 Special Relations: Equivalence Relations and Partial/Total Orders 436
8.5 Chapter at a Glance 453
9 Counting 457
9.1 Why You Might Care 458
9.2 Counting Unions and Sequences 459
9.3 Using Functions to Count 481
9.4 Combinations and Permutations 499
9.5 Chapter at a Glance 520
10 Probability 523
10.1 Why You Might Care 524
10.2 Probability, Outcomes, and Events 527
10.3 Independence and Conditional Probability 545
10.4 Random Variables and Expectation 567
10.5 Chapter at a Glance 591
11 Graphs and Trees 595
11.1 Why You Might Care 596
11.2 Formal Introduction 597
11.3 Paths, Connectivity, and Distances 623
11.4 Trees 641
11.5 Weighted Graphs 659
11.6 Chapter at a Glance 671
12 Looking Forward 675
References 679
Index 685

This textbook is designed for undergraduate students taking a course on the mathematical foundations of computer science. It is written from an exclusively CS perspective rather than for a mixed-discipline audience, helping CS students see the ways that foundational mathematical material is central to the discipline of computer science.

An Approachable Textbook Connecting The Mathematical Foundations Of Computer Science To Broad-ranging And Compelling Applications Throughout The Field.

2023-12-10