Discrete Mathematics for Computer Science Preliminary Edition
1st Edition
Published on 18. May 2015
Book
Paperback/Softback
684 pages
978-1-119-17109-6 (ISBN)
More details
Language
English
Place of publication
New York
United States
Target group
College/higher education
Dimensions
Height: 277 mm
Width: 211 mm
Thickness: 23 mm
Weight
1406 gr
ISBN-13
978-1-119-17109-6 (9781119171096)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
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 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
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