CS202DISCRETE MATHEMATICS4-0-0-8

Pre-requisites : NIL

Syllabus :
Set theory: sets, relations, functions, countability; Logic: formulae, interpretations, methods of proof, soundness and completeness in propositional and predicate logic; Number theory: division algorithm, Euclid's algorithm, fundamental theorem of arithmetic, Chinese remainder theorem, special numbers like Catalan, Fibonacci, harmonic and Stirling; Combinatorics: permutations, combinations, partitions, recurrences, generating functions; Graph Theory: paths, connectivity, subgraphs, isomorphism, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs; Algebraic Structures: semigroups, groups, subgroups, homomorphisms, rings, integral domains, fields, lattices and boolean algebras.

Texts :
1. C. L. Liu, Elements of Discrete Mathematics, 2nd Ed., Tata McGraw-Hill, 2000
2. R. C. Penner, Discrete Mathematics: Proof Techniques and Mathematical Structures, World Scientific, 1999.

References :
1.R. L. Graham, D E Knuth, and O Patashnik, Concrete Mathematics, 2nd Ed., Addison-Wesley, 1994.
2.K. H. Rosen, Discrete Mathematics & its Applications, 6th Ed., Tata McGraw-Hill, 2007.
3. J. L. Hein, Discrete Structures, Logic, and Computability, 3rd Ed., Jones and Bartlett, 2010.
4. N. Deo, Graph Theory, Prentice Hall of India, 1974.
5. S. Lipschutz and M. L. Lipson, Schaum's Outline of Theory and Problems of Discrete Mathematics, 2nd Ed., Tata McGraw-Hill, 1999.
6. J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.