CS206 Discrete Mathematics (3-1-0-8)

This course serves as a precursor to Algorithms. Students are taught the mathematical foundations and logic behind computer programming and algorithm design.

Pre-requisites - NIL

Course Content

Set theory: sets, functions, relations, partial orders, lattices.

Logic: propositional logic (formulae, truth tables, proof systems, soundness and completeness of proof systems), predicate logic (formulae, interpretations, proof systems, soundness and completeness of proof systems).

Combinatorics: permutations, combinations, partitions, Stirling numbers.

Recurrences, summations, generating functions, asymptotics.

Graph Theory: paths, connectivity, subgraphs, isomorphic and homeomorphic graphs, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs.

Algebraic Structures: semigroups, groups, subgroups, homomorphisms, rings, integral domains, fields.

Reference Books

1. J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 199

2. C. L. Liu, Elements of Discrete Mathematics, 2nd Ed, Tata McGraw-Hill, 2000.

3. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Ed, Addison-Wesley, 1994.

4. N. Deo, Graph Theory with Applications to Engineering and Computer Science, 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