## CS21001 Discrete Structures

### 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

### Syllabus

 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. Combinatorics 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.

### 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]

Home