CS21001 Discrete Structures 

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

Course schedule
Tutorial exercises

Course schedule

Class timing: Slot D (Mo 11:30-12:25, Tu 09:30-11:25, Th 07:30-08:25)

Class room: CSE 119

Instructor: Abhijit Das

Teaching assistants: Dipankar Das and Soumyajit Dey


Propositional logic

Syntax, semantics, valid, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments.

Proof techniques

Forward proof, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency.

Sets, relations
and functions

Operations on sets, relations and functions, binary relations, partial ordering relations, equivalence relations, principles of mathematical induction.

Size of a set

Finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument and the power set theorem, Schröder-Bernstein theorem.


Basic counting techniques: inclusion and exclusion, pigeon-hole principle, permutation, combination, summations. Introduction to recurrence relations and generating functions.

Algebraic structures
and morphisms

Algebraic structures with one binary operation - semigroups, monoids and groups, congruence relation and quotient structures. Free and cyclic monoids and groups, permutation groups, substructures, normal subgroups. Algebraic structures with two binary operations - rings, integral domains and fields. Boolean algebra and Boolean ring.

Graphs and trees

Graphs and their basic properties - degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees.


I plan to follow the following as the main text-book. More precisely, Chapters 1-6, 8 and 9 of this book would be covered. Admittedly, this book does not provide a satisfactory treatment of every topic in the official syllabus. But its coverage is quite decent, and the book is low-priced and handy.

Bernard Kolman, Robert C Busby, and Sharon Cutler Ross, Discrete Mathematical Structures, fifth edition, Prentice-Hall of India.

Some other books that can be used as references are:

Ralph P Grimaldi, Discrete and Combinatorial Mathematics, Pearson Education Asia.

Norman L Biggs, Discrete Mathematics, Oxford University Press.

Kenneth H Rosen, Discrete Mathematics and its Applications, Tata McGraw-Hill.

C L Liu, Elements of Discrete Mathematics, Tata McGraw-Hill.

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

Also look at the course page for Autumn 2005.

Tutorial exercises

Exercise set 1

Exercise set 2

Exercise set 3


Class Test 1 (Sep 12, 2006): Questions | Solutions

Mid-Semester Test (Sep 15, 2006): Questions | Solutions

Class Test 2 (Nov 15, 2006): Questions | Solutions

End-Semester Test (Nov 20, 2006): Questions | Solutions