CS210 - Discrete Mathematics

---

Course Description:
This course covers the mathematical foundations of computer science. The aim is to introduce the students to essential discrete structures such as propositions, predicates, sets, functions, sequences, and relations and fundamental principles and techniques of discrete mathematics, which may be employed in a variety of fields in computer science, including algorithms, data structures, theory of computation. The course also equips students with knowledge of concepts and skills that are building blocks in machine learning, databases, data science, cryptography, and networks. These include modeling problems with recurrence relations, counting, and graph and tree structures. A brief introduction to number theory and cryptography is made. A major focus of the course is on the formal and precise formulation of statements and methods of proof (including proofs by contradiction, contra-position, and mathematical induction). This course introduces students to essential problem-solving tools for tackling complex computational challenges. .

Prerequisites:

• Calculus-I, or Calculus with Theory

Textbook(s)/Supplementary Readings:

• Discrete Mathematics and its Applications Kenneth Rosen
• Invitation to Discrete Mathematics Jiřı́ Matoušek, Jaroslav Nešetřil
• Discrete Mathematics: Elementary and Beyond László Lovász, József Pelikán

Lectures:

Topic	Slides	Problem Sets
Introduction and Motivation How to succeed in this course Why Study Discrete Math?	Slides
Propositional Logic Proposition and truth value Compound proposition and truth table Implication and its derivative	Slides Slides Slides	PS
Logical Equivalence Tautology, Contradiction, Logical Equivalence Logical Equivalence using Truth Table Logical Equivalence using Laws	Slides Slides Slides	PS
Predicate Logic Predicates and Propositional Functions Universal and Existential Quantifiers Negating Quantified Statements Nested Quantifiers	Slides Slides Slides Slides	PS
Set Theory Sets: Definition, Universal Set, Complement, Cardinality Subset and Power Set Sets Operations Set Equality Characteristic Vectors: Sets as Bit-Vectors Multisets	Slides Slides Slides Slides Slides Slides	PS
Functions Ordered tuples and Cartesian Product Function and Representations Types of Functions Composition and Inverse of Function Numeric Functions	Slides Slides Slides Slides Slides	PS
Relations Relation: Definition and Notation Properties of Relations Combining Relations Operations on Relations: Projection and Join Equivalence Relation and Equivalence Classes Partial Order	Slides Slides Slides Slides Slides Slides	PS
Sequences and Sums Sequences and Progressions Summation and its linearity Evaluating Sums Evaluating Sums - Proofs without words Geometric Sums	Slides Slides Slides Slides Slides	PS
Proofs Proofs: Terminology and Rules of Inference Direct Proof Proof by Contrapositive Proof by Contradiction Proofs using Case Analysis	Slides Slides Slides Slides Slides	PS
Cardinality List Representation of Functions Properties of Functions as Lists Cardinality of Finite Sets Cardinality of Infinite Sets Countable and Uncountable Infinite Sets Diagonalization	Slides Slides Slides
Induction Principle of Mathematical Induction Proofs by Induction Proof by Induction Examples Strong Induction Well Ordering Principle	Slides Slides Slides Slides Slides	PS
Counting Introduction and Applications The Sum Rule The Product Rule The Complement Rule Inclusion-Exclusion Principle The Pigeon-Hole Principle Permutations and Combinations Combinatorial Proofs Permutation and Combinations with Repetitions	Slides Slides Slides Slides Slides Slides Slides Slides Slides	PS
Binomial Theorem and Pascal Triangle The Binomial Theorem The Pascal Triangle (or the al-Karaji triangle) Patterns in the Pascal Triangle (mod n)	Slides Slides Slides
Recurrence Relations Recursive Definition: Sequences Sets Functions Algorithms Recurrence Relations Solution of Recurrence Relations Proving Closed Form using Induction Substitution Method	Slides Slides Slides	PS
Graphs Graphs are everywhere Graph Types and Terminology: Handshaking Lemma Graph Representation, Complement, Transpose, Subgraph Walks, Paths and Cycles (Strongly) Connected Graphs, k-Connected Graphs Graphs Applications: BFS, DFS, Eulerian Graphs Graphs Applications in Optimization	Slides Slides Slides Slides Slides Slides Slides	PS
Special Classes of Graphs Complete Graphs, Path, Cycle, Star, Wheel, n-Cubes Bipartite Graphs Trees Characterization of Trees Minimum Spanning Tree Rooted Trees	Slides Slides Slides
Planar Graphs Planar Graphs and Planar Drawings Euler's Formula Boundaries of Regions Degrees of Region Face-Edge Handshaking Lemma Characterization of Planar Graph	Slides
Number Theory & Cryptography Divisibility and Congruence Modular Arithmetic and Applications GCD and Relative Primes Caesar Cipher and Affine Cipher, Modular Inverse The Chinese Remainder Theorem Fermat’s Little Theorem and Modular Exponentiation Public Key Cryptography and RSA Cryptosystem	Slides Slides Slides Slides Slides Slides Slides	PS

Back to Top