CS533DISCRETE MATHEMATICAL STRUCTURES4-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, 2/e, 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, 2/e, Addison-Wesley, 1994.
2. K H Rosen, Discrete Mathematics & its Applications, 6/e, Tata McGraw-Hill, 2007.
3. J L Hein, Discrete Structures, Logic, and Computability, 3/e, 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, 2/e, Tata McGraw-Hill, 1999.
6. J P Tremblay and R P Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.