Discrete Mathematics and Algorithms
Charles A. Cusack
David A. Santos
Version 2.5
December 21, 2015
,ii
, iii
Copyright c 2015 Charles A. Cusack. Permission is granted to copy, distribute and/or
modify this document under the terms of the GNU Free Documentation License,
Version 1.2 or any later version published by the Free Software Foundation; with no
Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the
license is included in the section entitled “GNU Free Documentation License”.
Copyright c 2007 David Anthony Santos. Permission is granted to copy, distribute
and/or modify this document under the terms of the GNU Free Documentation Li-
cense, Version 1.2 or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy
of the license is included in the section entitled “GNU Free Documentation License”.
History
• An Active Introduction to Discrete Mathematics and Algorithms, 2015, Charles A. Cusack.
Minor revisions. Algorithm Analysis chapter had major revisions.
• An Active Introduction to Discrete Mathematics and Algorithms, 2014, Charles A. Cusack.
This is a significant revision of the 2013 version (thus the slight change in title).
• An Introduction to Discrete Mathematics and Algorithms, 2013, Charles A. Cusack. This
document draws some content from each of the following.
– Discrete Mathematics Notes, 2008, David A. Santos.
– More Discrete Mathematics, 2007, David A. Santos.
– Number Theory for Mathematical Contests, 2007, David A. Santos.
– Linear Algebra Notes, 2008, David A. Santos.
– Precalculus, An Honours Course, 2008, David Santos.
These documents are all available from http://www.opensourcemath.org/books/santos/,
but the site appears not to be consistently available.
,iv
Contents
Preface vii 7 Algorithm Analysis 195
7.1 Asymptotic Notation . . . . . . . . . . 195
How to use this book ix 7.1.1 The Notations . . . . . . . . . 195
7.1.2 Properties of the Notations . . 205
1 Motivation 1 7.1.3 Proofs using the definitions . . 209
1.1 Some Problems . . . . . . . . . . . . . 2 7.1.4 Proofs using limits . . . . . . . 214
7.2 Common Growth Rates . . . . . . . . 225
2 Proof Methods 7 7.3 Algorithm Analysis . . . . . . . . . . . 233
2.1 Direct Proofs . . . . . . . . . . . . . . 7 7.3.1 Common Time Complexities . 253
2.2 Implication and Its Friends . . . . . . 16 7.4 Problems . . . . . . . . . . . . . . . . 258
2.3 Proof by Contradiction . . . . . . . . . 20
2.4 Proof by Contraposition . . . . . . . . 29 8 Recursion, Recurrences, and Mathe-
2.5 Other Proof Techniques . . . . . . . . 31 matical Induction 263
2.6 If and Only If Proofs . . . . . . . . . . 33 8.1 Mathematical Induction . . . . . . . . 263
8.1.1 The Basics . . . . . . . . . . . 264
2.7 Common Errors in Proofs . . . . . . . 35
8.1.2 Equalities/Inequalities . . . . . 269
2.8 More Practice . . . . . . . . . . . . . . 38
8.1.3 Variations . . . . . . . . . . . . 272
2.9 Problems . . . . . . . . . . . . . . . . 42
8.1.4 Strong Induction . . . . . . . . 276
8.1.5 Induction Errors . . . . . . . . 278
3 Programming Fundamentals and Algo-
8.1.6 Summary/Tips . . . . . . . . . 280
rithms 45
8.2 Recursion . . . . . . . . . . . . . . . . 283
3.1 Algorithms . . . . . . . . . . . . . . . 45
8.3 Solving Recurrence Relations . . . . . 291
3.2 The mod operator and Integer Division 49
8.3.1 Substitution Method . . . . . . 293
3.3 If-then-else Statements . . . . . . . 56 8.3.2 Iteration Method . . . . . . . . 297
3.4 The for loop . . . . . . . . . . . . . . 58 8.3.3 Master Theorem . . . . . . . . 305
3.5 Arrays . . . . . . . . . . . . . . . . . . 61 8.3.4 Linear Recurrence Relations . . 307
3.6 The while loop . . . . . . . . . . . . . 65 8.4 Analyzing Recursive Algorithms . . . 311
3.7 Problems . . . . . . . . . . . . . . . . 68 8.4.1 Analyzing Quicksort . . . . . . 315
8.5 Problems . . . . . . . . . . . . . . . . 319
4 Logic 71
4.1 Propositional Logic . . . . . . . . . . . 71 9 Counting 323
4.1.1 Compound Propositions . . . . 73 9.1 The Multiplication and Sum Rules . . 323
4.1.2 Truth Tables . . . . . . . . . . 80 9.2 Pigeonhole Principle . . . . . . . . . . 328
4.1.3 Precedence Rules . . . . . . . . 82 9.3 Permutations and Combinations . . . 334
4.2 Propositional Equivalence . . . . . . . 84 9.3.1 Permutations without Repeti-
4.3 Predicates and Quantifiers . . . . . . . 96 tions . . . . . . . . . . . . . . . 334
4.4 Normal Forms . . . . . . . . . . . . . . 105 9.3.2 Permutations with Repetitions 337
9.3.3 Combinations without Repeti-
4.5 Bitwise Operations . . . . . . . . . . . 108
tions . . . . . . . . . . . . . . . 341
4.6 Problems . . . . . . . . . . . . . . . . 111
9.3.4 Combinations with Repetitions 347
9.4 Binomial Theorem . . . . . . . . . . . 351
5 Sets, Functions, and Relations 117
9.5 Inclusion-Exclusion . . . . . . . . . . . 354
5.1 Sets . . . . . . . . . . . . . . . . . . . 117
9.6 Problems . . . . . . . . . . . . . . . . 360
5.2 Set Operations . . . . . . . . . . . . . 123
5.3 Functions . . . . . . . . . . . . . . . . 134 10 Graph Theory 365
5.4 Partitions and Equivalence Relations . 145 10.1 Types of Graphs . . . . . . . . . . . . 365
5.5 Problems . . . . . . . . . . . . . . . . 159 10.2 Graph Terminology . . . . . . . . . . . 369
10.3 Some Special Graphs . . . . . . . . . . 374
6 Sequences and Summations 163 10.4 Handshaking Lemma . . . . . . . . . . 377
6.1 Sequences . . . . . . . . . . . . . . . . 163 10.5 Graph Representation . . . . . . . . . 379
6.2 Sums and Products . . . . . . . . . . . 176 10.6 Problem Solving with Graphs . . . . . 380
6.3 Problems . . . . . . . . . . . . . . . . 192 10.7 Traversability . . . . . . . . . . . . . . 383