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)

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.

  1. Discrete Mathematics and its Applications (Kenneth H. Rosen)
  2. 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]
  • Section 1.1 - Rosen
Lecture #3
Wed 06/08 		Knights and Knaves • Implication and examples
[slides]
  • Sections 1.1, 1.2 - Rosen
Lecture #4
Fri 08/08 		Tautologies and contradictions • Logical equivalence - examples
  • Sections 1.3 - Rosen
Lecture #5
Mon 11/08 		Inference rules and argument forms • Example applications of inference rules
[slides]
  • Section 1.6 - Rosen
Lecture #6
Tue 12/08 		Inference rules and argument forms - fallacies • Axioms, proofs and tautologies • Predicate logic
  • Sections 1.4, 1.6 - Rosen
 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
  • Sections 1.4, 1.5 - Rosen
Lecture #8
Tue 19/08 		Predicate logic - examples • Validity and logical equivalence
  • Sections 1.4, 1.5 - Rosen
Lecture #9
Wed 20/08 		Validity and logical equivalences - models, interpretations, examples
  • Sections 1.4, 1.5 - Rosen
Lecture #10
Fri 22/08 		Validity, inference rules and arguments in predicate logic
  • Sections 1.4, 1.5, 1.6 - Rosen
 PS2 released
Lecture #11
Mon 25/08 		Inference rules and arguments in predicate logic • Axioms and proofs
  • Section 1.6 - Rosen
Tutorial #2
Tue 26/08 		Based on Problem set 2
No matching items