CS21001 Discrete Structures

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

Course schedule
Syllabus
References
Tutorial exercises
Tests

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

Syllabus

 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, relationsand 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. Combinatorics Basic counting techniques: inclusion and exclusion, pigeon-hole principle, permutation, combination, summations. Introduction to recurrence relations and generating functions. Algebraic structuresand 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.

References

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.

Tests

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

Home