## CS21001 Discrete Structures, Autumn 2007

### L-T-P: 3-1-0, Credits: 4

Course schedule
Syllabus
References
Tutorial exercises
Tests

### Course schedule

Time: Slot D (M 11:30-12:25, Tu 09:30-11:25, Th 07:30-08:25)

Top

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

Top

### References

The following is the main text-book for the course. This book provides a comprehensive and modern treatment of the subject and would be an extremely handy reference for all your years to come. Unfortunately, the book omits many proofs and has no exercises. This means that attending the lectures regularly would be a must for every student.

Kenneth H Rosen (Editor-in-chief), Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.

Some other books that can be used as references are:

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

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

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

Norman L Biggs, Discrete Mathematics, Oxford University Press.

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

#### Augmenting hand-outs

• Size of a set
Note that this document was prepared in the last year when 0 was not a natural number. Now that 0 is a natural number, please incorporate the relevant changes.

Top

Top

Top

Home