Discrete Structures (MA101.5) - Monsoon Semester 2024

This is a core undergraduate course on Discrete Mathematics for incoming undergraduate students (UG-1).  I will co-teach this course with Kannan Srinathan (who will cover the second half).  The topics covered include:

Unit 1: Propositional Logic, Sets, Relations, Functions, Counting,  Proof techniques, Cantor's number and infinite sets.

Unit 2: Elementary Group Theory, Rings and Fields, Finite fields over Primes.

Unit 3: Recurrence Relations, generating functions.

Unit 4: Elementary Probability Theory, Birthday attacks. Application to hash functions.

Unit 5: Elementary Graph Theory.

I will cover Unit 1, Unit 3, and Unit 5, while Srinathan will cover the rest. The prerequisites for the course are minimal (familiarity with high school mathematics).


Course Format: 

The course commences on 30th July 2024. The lectures and tutorials will be held in person in Room SH1 (Sec. A) and SH2 (Sec. B).


Schedule: 


Evaluation:


In the first half, there will be two theory assignments (30% weightage) and two proctored exams: one quiz (32% weightage) and one final exam (38% weightage).



Teaching Associates: TBA


Lecture slides:

Lecture 1, Lecture 2, Lecture 3: Propositional and first-order logic.

Lecture 4, Lecture 5, Lecture 6: Proof Techniques.

Lecture 7, Lecture 8, Lecture 9: Elementary Set Theory and Functions.

Lecture 10, Lecture 11, Lecture 12: Infinite Sets, Cantor's diagonalization, Continuum Hypothesis.

Lecture 13, Lecture 14, Lecture 15: Counting techniques, Permutations and Combinations, Inclusion-Exclusion principle, Pigeonhole principle.

Lecture 16, Lecture 17, Lecture 18: Elementary Graph Theory.


Assignments:

TBA


Quiz

TBA


Final Exam

TBA


References