• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 4 out of 454 pages
Summary

Summary An Active Introduction to Discrete Mathematics and Algorithms – Lecture Notes | Computer Science, Logic and Algorithm Design

Document preview thumbnail
Preview 4 out of 454 pages

Master essential concepts in **An Active Introduction to Discrete Mathematics and Algorithms [Lecture Notes]**, a valuable academic study resource covering the mathematical foundations of computer science and algorithm development. These lecture notes introduce important principles of discrete mathematics, logical reasoning, mathematical problem-solving, and algorithm design. They are useful for students looking to strengthen their understanding of computational thinking and theoretical computer science. **Key topics include:** - Fundamentals of discrete mathematics - Mathematical logic and propositional reasoning - Sets, relations, and functions - Mathematical proofs and induction - Counting principles and combinatorics - Graph theory and applications - Algorithms and problem-solving techniques - Algorithm analysis and complexity - Discrete structures in computer science **Ideal for:** - Computer science students - Information technology students - Software engineering students - Mathematics students - Data science learners - University students preparing for examinations These lecture notes provide a useful foundation for understanding discrete mathematical structures, logical reasoning, and algorithmic problem-solving in computer science.

Content preview

An Active Introduction to
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

Document information

Uploaded on
November 21, 2026
Number of pages
454
Written in
2026/2027
Type
Summary
$19.99

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
Maliah
3.6
(18)
Sold
93
Followers
39
Items
2004
Last sold
4 days ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions