Lectures in Discrete Mathematics

✍ Scribed by Edward A. Bender, S. Gill Williamson

• Publisher: UC San Diego
• Year: 2019
• Tongue: English
• Leaves: 503
• Category: Library

✦ Table of Contents

Boolean Functions & Computer Arithmetic......Page 2
1 Boolean Functions......Page 3
Exercises for Section 1......Page 10
2 Number Systems & Computer Arithmetic......Page 11
Computer Arithmetic......Page 13
Exercises for Section 2......Page 22
Multiple Choice Questions for Review......Page 25
Logic......Page 31
1 Propositional Logic......Page 32
Implication......Page 35
Exercises for Section 1......Page 40
2 Predicate Logic......Page 43
Exercises for Section 2......Page 50
Multiple Choice Questions for Review......Page 54
Number Theory & Cryptography......Page 60
1 Basic Facts about Numbers......Page 61
Prime Numbers & Factorization......Page 62
Remainders & Modular Arithmetic......Page 66
Floor & Ceiling Functions......Page 69
Exercises for Section 1......Page 70
Basic Ideas......Page 73
gcd, lcm & φ Functions......Page 76
Cryptography on the Internet......Page 80
Exercises for Section 2......Page 84
Multiple Choice Questions for Review......Page 86
Sets & Functions......Page 92
1 Sets......Page 93
Set Properties & Proofs......Page 94
Ordering Sets......Page 98
Subsets of Sets......Page 101
Exercises for Section 1......Page 104
2 Functions......Page 107
Exercises for Section 2......Page 117
Multiple Choice Questions for Review......Page 121
Equivalence & Order......Page 129
1 Equivalence......Page 130
Pigeonhole Principle......Page 134
Exercises for Section 1......Page 139
2 Order......Page 141
New Posets from Old Ones......Page 146
More Poset Concepts......Page 154
Exercises for Section 2......Page 160
Multiple Choice Questions for Review......Page 163
Induction, Sequences & Series......Page 169
1 Induction......Page 170
More Advanced Examples of Induction......Page 173
Exercises for Section 1......Page 178
2 Infinite Sequences......Page 181
3 Infinite Series......Page 189
Exercises for Section 3......Page 199
Multiple Choice Questions for Review......Page 200
Solutions......Page 206
Counting & Listing......Page 245
1 Lists with Repetitions......Page 246
Exercises for Section 1......Page 252
2 Lists without Repetition......Page 254
Exercises for Section 2......Page 257
3 Sets......Page 258
Exercises for Section 3......Page 271
4 Probability & Basic Counting......Page 273
Exercises for Section 4......Page 282
Multiple Choice Questions for Review......Page 286
Functions......Page 293
1 Basic Terminology......Page 294
Exercises for Section 1......Page 299
2 Permutations......Page 300
Exercises for Section 2......Page 306
Inverse of Arbitrary Function......Page 307
Monotonic Lists & Unordered Lists......Page 309
Exercises for Section 3......Page 312
4 Functions & Probability......Page 314
Random Variables......Page 315
Joint Distributions......Page 321
Independence......Page 322
Standard Distributions......Page 327
Exercises for Section 4......Page 332
Multiple Choice Questions for Review......Page 334
Decision Trees & Recursion......Page 342
1 Basic Concepts of Decision Trees......Page 343
What is Decision Tree......Page 344
Permutations......Page 348
Traversing Decision Trees......Page 349
Exercises for Section 1......Page 355
2 Recursive Algorithms......Page 357
Exercises for Section 2......Page 368
3 Decision Trees & Conditional Probability......Page 369
Generating Objects at Random......Page 377
First Moment Method & SAT Problem......Page 379
Exercises for Section 3......Page 382
Induction......Page 384
Recursive Equations......Page 386
Exercises for Section 4......Page 393
Multiple Choice Questions for Review......Page 395
Graph Theory......Page 404
1 What is Graph......Page 405
Random Graphs......Page 412
Exercises for Section 1......Page 415
2 Digraphs, Paths & Subgraphs......Page 418
Exercises for Section 2......Page 427
3 Trees......Page 429
Spanning Trees......Page 435
Exercises for Section 3......Page 439
4 Rates of Growth & Analysis of Algorithms......Page 441
Polynomial Time Algorithms......Page 447
Theorem for Recursive Algorithms......Page 449
Exercises for Section 4......Page 453
Multiple Choice Questions for Review......Page 456
Solutions......Page 465