CS210 - Discrete Mathematics
Course Description:
This course covers the mathematical foundations of computer science.
It provides an introduction to logic, sets, functions, sequences, relations,
proofs, combinatorics, graphs, trees, number theory, and discrete probability.
The aim is to introduce the students to the fundamental techniques and principles of discrete mathematics,
which may be employed in a variety of mathematical and computing disciplines, including algorithms,
data structures, databases, networks, and complexity theory. Students learn how to formulate,
model, and solve computational problems with various discrete structures.
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
|
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