CS21001 Discrete Structures 

 Autumn 2005, L-T-P: 3-1-0, Credits: 4 


Class timings

Slot: D
Lecture: M 11:30-12:25, Tu 9:30-11:25
Tutorial: Th 7:30-8:25
Room No: CSE 119


Set theory and logic  

Logic and propositions, sets, set operations, functions, relations, equivalence relations, partial orders, induction and recursion, finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument, integers, rationals and real numbers.


Pigeon-hole principle, permutations and combinations, summations, principal of inclusion-exclusion, designs, generating functions, linear recurrences and their solutions, divide-and-conquer relations.

Algebraic structures  

Groups and subgroups, morphisms, permutations, rings, domains, fields, polynomials, finite fields, error correcting codes, lattices, Boolean algebra.

Recommended books

The following book will be mostly followed in the course:

Norman L Briggs, Discrete mathematics, second edition, Oxford University Press.

Some other good books are:

J P Tremblay and R Manohar, Discrete mathematical structures with applications to Computer Science, Tata McGraw-Hill Publishing Company, 1999.

C L Liu, Elements of discrete mathematics, 2nd edition, Tata McGraw-Hill Publishing Company, 2000.

Additional hand-outs may also be provided in the class.

Notes on ideals and quotient rings: pdf, ps.

Practice exercises

  • Exercise Set 1 : pdf, ps.
  • Exercise Set 2 : pdf, ps.
  • Exercise Set 3 : pdf, ps.
  • Exercise Set 4 : pdf, ps.
  • Exercise Set 5 : pdf, ps.

Test papers

  • Class test 1: September 08, 2005.
    Questions [pdf, ps]    Solutions [pdf, ps]

  • Mid-semester test: September 16, 2005.
    Questions [pdf, ps]    Solutions [pdf, ps]

  • Class test 2: November 10, 2005.
    Questions [pdf, ps]    Solutions [pdf, ps]

  • End-semester test: November 21, 2005.
    Questions [pdf, ps]    Solutions [pdf, ps]