CS1200 Discrete Mathematics for CS - I
July - Nov 2025
Coordinates
- Where: SSB 134
- When: C slot - Mon (10 am), Tue (9 am), Wed (8 am), Fri (12 pm)
Course staff
- Instructor: Yadu Vasudev (yadu@cse.iitm.ac.in)
- TAs:
- Alan (cs24m006@smail)
- Aditya (cs25m007@smail)
- Drone (cs22b005@smail)
- Kunal (cs25s020@smail)
- Mihir (cs22b004@smail)
- Nagashri (cs21d004@smail)
- Sutanay (cs21d005@smail)
- Swapnil (cs25m051@smail)
Important links
- Moodle
- Ed Discussions
Join using your smail/iitm ids via this link - Anonymous course feedback
Course calendar
About this course
Design of computer systems involve describing specifications of the systems, developing algorithms that meet the specifications, and developing the actual system/program that implements the algorithms. At each step of this process, we require a way to describe the system in a formal/mathematical way so that the solutions can then be verified. We will study the underlying mathematical abstractions that are necessary to perform these tasks, and methods to mathematically prove the correctness of our designs/constructions.
This course is mathematical in nature, and will require you to state and prove theorems. You will not be actually designing computer systems in the course, but the topics are motivated by the applications that you will see in computer science.
Prerequisites - There are no formal prerequisites for the course, apart from high-school mathematics. This course together with CS1202 (Discrete Math for CS - II) form a prerequisite for almost all courses in the CS curriculum.
Course contents
The course will look at the following three broad themes. The order of the topics covered may vary.
- Sets, logic and proofs - Representation of sets, propositional and predicate logic, truth tables, deduction and resolution, mathematical proofs, infinite sets - countable and uncountable sets, Cantor’s diagonalization, mathematical induction
- Counting and combinatorics - Sum and product rule, principle of inclusion-exclusion, pigeonhole principle, double counting and counting by bijections, recurrence relations, generating functions
- Structures on sets - relations, functions, graphs and trees, posets, lattices, and Haase diagrams, fixed points
Course resources
Our main sources of reference will be the following textbooks.
- Discrete Mathematics and its Applications (Kenneth H. Rosen)
- Mathematics for Computer Science (Eric Lehman, F. Thomas Leighton, Albert R. Meyer)
Apart from this, there are a lot of resources available online. We may refer to them occasionally. Both the books contain a number of exercise problems for practice.
Weekly schedule
There are four lecture slots per week. We will have tutorials and short exams after every 5-6 lectures. The exact schedule is given in the course calendar that is shared. The tutorials are ungraded and meant for solving practice problems associated with the concepts taught during the lectures. They are vital for gaining better understanding of the material and must not be missed.
Apart from the tutorials, you are welcome to use the course discussion forum to clarify doubts with the instructor and the TAs.
Grading policy (tentative)
- Short exams: 3*10 = 30%
- Quizzes: 2*15 = 30%
- End-semester exam = 40%
Important dates (tentative)
- Tutorials (ungraded): Aug 13, Aug 25, Sep 10, Sep 22, Oct 3, Oct 15, Oct 29, Nov 11
- Short exams: Aug 29, Oct 1, Nov 3
- Quizzes (according to institute calendar): Sep 3, Oct 8
- End-semester (according to institute calendar): Nov 18
Communication
Please sign up on the course discussion forum here. This will be the first point of contact for any issues related to the course. For general questions related to the course (any comments/doubts), please create a thread in the correct category and add your question/comment there. You are encouraged to reply and clear the doubts of your friends. To encourage this interaction, the forum supports anonymous posts and answers. Please be courteous to others when you are posting anonymously.
| Date | Lecture | References | Misc |
|---|---|---|---|
| Lecture #1 Fri 01/08 |
Introduction to the course • Admin and logistic details [slides] |
Sign up on Ed Discussions | |
| Lecture #2 Tue 05/08 |
Propositions and truth values • Compound propositions and their truth values • Knights and Knaves [slides] |
|
|
| Lecture #3 Wed 06/08 |
Knights and Knaves • Implication and examples [slides] |
|
|
| Lecture #4 Fri 08/08 |
Tautologies and contradictions • Logical equivalence - examples |
|
|
| Lecture #5 Mon 11/08 |
Inference rules and argument forms • Example applications of inference rules [slides] |
|
|
| Lecture #6 Tue 12/08 |
Inference rules and argument forms - fallacies • Axioms, proofs and tautologies • Predicate logic |
|
PS1 released |
|
Tutorial #1 Wed 13/08 |
Based on Problem set 1 | ||
| Lecture #7 Mon 18/08 |
Predicate logic - domain of discourse, examples, quantifiers, negation |
|
|
| Lecture #8 Tue 19/08 |
Predicate logic - examples • Validity and logical equivalence |
|
|
| Lecture #9 Wed 20/08 |
Validity and logical equivalences - models, interpretations, examples |
|
|
| Lecture #10 Fri 22/08 |
Validity, inference rules and arguments in predicate logic |
|
PS2 released |
| Lecture #11 Mon 25/08 |
Inference rules and arguments in predicate logic • Axioms and proofs |
|
|
|
Tutorial #2 Tue 26/08 |
Based on Problem set 2 | ||
|
Test #1 Fri 29/08 |
Based on Lectures 1 - 11 (Problem sets 1 and 2) | ||
| Lecture #12 Mon 01/09 |
Direct and indirect proofs - examples |
|
|
| Lecture #13 Tue 02/09 |
Indirect proof and proofs by contradiction - examples |
|
|
|
Quiz #1 Wed 03/09 |
Based on Lectures 1 - 11 (Problem sets 1 and 2) | ||
| Lecture #14 Mon 08/09 |
Non-constructive proofs, proof by cases, mathematical induction |
|
|
| Lecture #15 Tue 09/09 |
Principle of mathematical induction - examples, strong induction |
|
|
| Lecture #16 Wed 10/09 |
Induction and well-ordering - examples, equivalence [notes] |
|
PS3 released |
|
Tutorial #3 Fri 12/09 |
Based on Problem set 3 | ||
| Lecture #17 Mon 15/09 |
Sets and operations on sets, relations - examples |
|
|
| Lecture #18 Tue 16/09 |
Functions on sets, cardinality and countable sets |
|
|
| Lecture #19 Wed 17/09 |
More examples of countable sets and their properties |
|
|
|
Tutorial #4 Thu 18/09 |
Discussion of Problem set 3 | ||
| Lecture #20 Fri 19/09 |
More examples of countable sets • Uncountable sets - Cantor's diagonalization |
|
|
| Lecture #21 Mon 22/09 |
More examples of uncountable sets • Diagonalization in computer science - the halting problem |
|
PS4 released |
| Lecture #22 Tue 23/09 |
Basic counting - product rule, sum rule, bijections |
|
|
|
Tutorial #5 Wed 24/09 |
Based on Problem set 4 | ||
| Lecture #23 Fri 26/09 |
Double counting - examples • Binomial identities using double counting |
|
|
| Lecture #24 Mon 29/09 |
Binomial theorem - combinatorial proof and proof by induction • Counting by bijections - examples |
|
|
| Lecture #25 Tue 30/09 |
Counting by bijections - Catalan numbers |
|
|
|
Test #2 Wed 01/10 |
Based on Lectures 12 - 21 (Problem sets 3 and 4) | ||
| Lecture #26 Fri 03/10 |
Counting by bijections - Catalan numbers (contd.) |
|
|
|
Tutorial #6 Mon 06/10 |
Based on Problem set 5 | ||
| Lecture #27 Tue 07/10 |
Multisets and multichoosing - examples and equivalences • Multinomial coefficients and balls into bins |
|
|
|
Quiz #2 Wed 08/10 |
Based on Lectures 12 -26 (Problem sets 3, 4, and 5) | ||
| Lecture #28 Fri 10/10 |
Balls into bins • PIE - examples, number of onto functions |
|
|
| Lecture #29 Mon 13/10 |
Principle of Inclusion-Exclusion - partitions and Stirling numbers, derangements |
|
|
| Lecture #30 Tue 14/10 |
PIE - examples • Recurrence relations - examples |
|
PS6 released |
| Lecture #31 Wed 15/10 |
Recurrence relations - examples • Guessing and verifying solutions to recurrence relations |
|
|
| Lecture #32 Thu 16/10 |
Linear recurrence relations and their solutions • Generating functions |
|
|
|
Tutorial #7 Fri 17/10 |
Based on Problem set 6 | ||
| Lecture #33 Fri 24/10 |
Generating functions - Catalan numbers and derangements |
|
PS7 released |
| Lecture #34 Mon 27/10 |
Pigeonhole principle and its applications |
|
|
| Lecture #35 Tue 28/10 |
Pigeonhole principle and its applications (contd.) |
|
PS8 released |
|
Tutorial #8 Wed 29/10 |
Based on Problem set 7 | ||
| Lecture #36 Thu 30/10 |
Relations on sets and their properties - examples |
|
|
| Lecture #37 Fri 31/10 |
Transitive relations, composition of relations, boolean matrix multiplication and application in computing transitive closure |
|
|
|
Test #3 Mon 03/11 |
Based on Lectures 27 - 33 (Problem sets 6 and 7) | ||
| Lecture #38 Tue 04/11 |
Transitive closure and boolean matrix multiplication • Equivalence relations - examples, properties |
|
|
| Lecture #39 Thu 06/11 |
Equivalence relations and partitions - examples, Bell numbers • Posets - examples and properties |
|
|
| Lecture #40 Fri 07/11 |
Posets - chains, antichains, decompositions, examples |
|
PS9 released |
| Lecture #41 Mon 10/11 |
Posets - chains and antichains • Dilworth's/Mirsky's theorem and application • Wrap-up of the course |
|
|
|
Tutorial #9 Tue 11/11 |
Based on Problem sets 8 and 9 |