MTL1080: Discrete Mathematicsl Structures
Spring semester, 2025-26
Lectures by:
Prof. Dalu Jacob, for Section I, and
Ashutosh Rai, for Section II.
Time of the class:
Mondays and Tuesdays, 2:00pm - 3:20pm in LH519 (Section I) and in LH611 (Section II).
Office hours:
by email appointment.
Teaching assistants:
Sahiba: maz238701@maths.iitd.ac.in
Cathein Bernard: maz248180@iitd.ac.in
Maalav Mehta: mt1221265@iitd.ac.in
Akshat Chaudhary: mt6210814@iitd.ac.in
Tutorials:
On Wednesdays, 2pm-3pm in LH606 (Section I) and LH611 (Section II).
Syllabus: We will roughly cover the following topics: Logic: propositional logic: language of propositional logic, truth table, natural deduction, predicate logic: language of predicate logic, logical inference with quantifiers. Proof techniques: introduction to different standard proof techniques. Set theory: review of basic set operations, cardinality of a set. Relations: types of relations, operations of relations and applications, posets, topological ordering; congruence arithmetic. Combinatorics: counting techniques: pigeon hole principle, inclusion exclusion principle, recurrence relation and generating function. Graph theory: graph as a discrete structure, modeling applications using graphs, Hamiltonian graphs, planar graphs, graph coloring, matching.
Course Material:
We will mostly follow the book "Discrete Mathematics and its Applications" by Kenneth H. Rosen [Ros] published by McGraw Hill. A low price edition is available in India. There are many editions available, and it would not make much difference if you cannot find the latest one. The references below are from 8th Edition.
In addition, "Mathematics for Computer Science" book at MIT OpenCourseware can also be referred for some topics. The book is freely available here.
Any other course material, if needed, will be told in the class and in references below.
Credits:
The course will be evaluated on a 100 point scale.
5 points will be for attendance. Students having at least 85% of attendacne will get 5 points, and 80-85% will get 2 points, and ones with less than 80% attendance will not get any points (out of 5).
The minor and major will be worth 30 and 35 points respectively.
The quizzes will be worth 30 points.
To audit pass the course, you need to have at least 40 points, at least 30 of which should come from minor and major.
There will be only one make-up exam to make up for missed quizzes or minor. One can appear in at most one make-up exam, either the re-quiz or the re-minor, both of which will be conducted before the major, and would contain the full syllabus.
Attendance of 75% is required to get credits for the course.
Lectures and References:
Lecture 0: Logistic and introduction to the course: why study Discrete Mathematics.
Lecture 1: Popositional logic and applications. Reference: [Ros] 1.1 and 1.2.
Lecture 2: Popositional equivalences, Satisfiability, Applications of Satisfiability. Reference: [Ros] 1.3.
Lecture 3: Predicates and quantifiers, nested quantifiers. Reference: [Ros] 1.4, 1.5.
| |