CS1200 - Discrete Mathematics for Computer Science

Course Data :


  • Sets and Sequences : Data Models. - 3L+1T
    Finite Sets, Power Set, Cardinality of finite sets, Cartesian Product, Properties of Sets, Vector Implementations of Sets.
  • Describing Sets : Logic & Proofs - 15L + 3T
    Introduction to Logic. Propositional Logic, Truth tables, Deduction, Resolution, Predicates and Quantifiers, Mathematical Proofs. Infinite sets, well-ordering. Countable and Uncountable sets, Cantor's diagonalization. Mathematical Induction - weak and strong induction.
  • Relational Structures on Sets : Relations & Graphs - 9L + 2T
    Relations, Equivalence Relations. Functions, Bijections. Binary relations and Graphs. Trees (Basics). Posets and Lattices, Hasse Diagrams. Boolean Algebra.
  • Sizes of Sets : Counting & Combinatorics - 12L + 3T
    Counting, Sum and product rule, Principle of Inclusion Exclusion. Pigeon Hole Principle, Counting by Bijections. Double Counting. Linear Recurrence relations - methods of solutions. Generating Functions. Permutations and counting.
  • Structured Sets : Algebraic Structures - 6L + 2T
    Structured sets with respect to binary operations. Groups, Semigroups, Monoids. Rings, and Fields. Vector Spaces, Basis.


  • Discrete Mathematics and its Applications - Kenneth H. Rosen 7th Edition -Tata McGraw Hill Publishers - 2007


  • Elements of Discrete Mathematics, C. L Liu, McGraw-Hill Inc, 1985. Applied Combinatorics, Alan Tucker, 2007.
  • Concrete Mathematics, Ronald Graham, Donald Knuth, and Oren Patashnik, 2nd Edition - Pearson Education Publishers - 1996.
  • Combinatorics: Topics, Techniques, Algorithms by Peter J. Cameron, Cambridge University Press, 1994 (reprinted 1996).
  • Topics in Algebra, I.N. Herstein, Wiley, 1975.

Learning Outcomes Expected:

After completing the course, the student will be able to:
  • Use logical notation to define and reason mathematically about the fundamental data types and structures (such as numbers, sets) used in computer algorithms and systems.
  • Comprehend and Evaluate rigor in the definitions and conclusions about mathematical models and identify fallacious reasoning and statements. Identify and Apply properties of combinatorial structures and properties - know the basic techniques in combinatorics and counting.
  • Analyze sets with operations, and identify their structure. Reason and Conclude properties about the structure based on the observations.
  • Gain the conceptual background needed to be able to identify structures of algebraic nature, and discover, prove and use properties about them.




Credits Type Date of Introduction
3-1-0-0-6-10 Core Jul 2015

Previous Instances of the Course

© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits