Discrete Structures and Computation (Spring 2025)

Course Material

(Lecture notes are uploaded in the “Google classroom” for the course. Drop me an email if you want to access them.)

Discrete Mathematics and its Applications: with combinatorics and graph theory
- 7th edition by Kenneth H. Rosen (Indian adaptation by Kamala Krithivasan) (ISBN-13: 978-0070681880)
- Tata Mcgraw-Hill Education

(Note: Topics within the modules might change)

Module 1: Sets and Logic
- Operations on sets, Functions, Relations
- Countability, Mathematical induction
- Logical formulas and sentences
- Basic logical operations, Quantifiers
Module 2: Counting
- Pigeonhole, Inclusion-Exclusion
- Binomial Coefficients, Bijections
- Linear recurrences, Geometric series
- Master Theorem, Generating Functions
Module 3: Basic Graph Theory
- Representations, Connectivity, Cycles, Trees
- Spanning trees, Matchings, Eulerian and Hamiltonian paths
- Independent sets, Cliques, Colouring
- Dominating sets, Planar graphs, Directed graphs, Tournaments
Module 4: Arithmetic Algorithms
- Addition, Multiplication, Computing GCD
- Primality, Integer Factoring, RSA
- Additional topics (if time permits)