# Discrete Mathematics for M.Tech. (CS) (July 2014-November 2014)

Time: Monday and Wednesday, 9.30am-11.10am.

Where: S.N. Bose Bhavan, 7th floor, Room No 704-705.

Marking policy: 30 Midsemester, 50 End Semester, 5 scribe and 15 for assignments (term paper for Ph. D. Students).

## Syllabus

Combinatorics: Multinomial theorem, principle of inclusion exclusion; Recurrence relations - classification, summation method, extension to asymptotic solutions from solutions for subsequences; Linear homogeneous relations, characteristic root method, general solution for distinct and repeated roots, non-homogeneous relations and examples, generating functions and their application to linear homogeneous recurrence relations, non-linear recurrence relations, exponential generating functions, brief introduction to Polya theory of counting.

Graph Theory: Graphs and digraphs, complement, isomorphism, connectedness and reachability, adjacency matrix, Eulerian paths and circuits in graphs and digraphs, Hamiltonian paths and circuits in graphs and tournaments, trees; Minimum spanning tree, rooted trees and binary trees, planar graphs, Euler's formula, statement of Kuratowskey's theorem, dual of a planer graph, independence number and clique number, chromatic number, statement of Four-color theorem, dominating sets and covering sets.

Logic: Propositional calculus: propositions and connectives, syntax; Semantics: truth assignments and truth tables, validity and satisfiability, tautology; Adequate set of connectives; Equivalence and normal forms; Compactness and resolution; Formal reducibility - natural deduction system and axiom system; Soundness and completeness.

Introduction to Predicate Calculus: Syntax of first order language; Semantics: structures and interpretation; Formal deductibility; First order theory, models of a first order theory (definition only), validity, soundness, completeness, compactness (statement only), outline of resolution principle.

## References

We will use the following texts.
1. Fred Roberts and Barry Tesman: Applied Combinatorics, Second Edition, CRC Press, 2009.
2. J. H. van Lint and R. M. Wilson: A Course in Combinatorics, Second Edition, Cambridge University Press, 2001.
3. C. L. Liu: Elements of Discrete Mathematics, 2nd ed., McGraw Hill, New Delhi, 1985.
4. R. A. Brualdi: Introductory Combinatorics, North-Holland, New York, 1977.
5. Douglas B. West: Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.
6. J. A. Bondy and U. S. R. Murty: Graph Theory with Applications, Macmillan Press, London, 1976.
7. E. Mendelsohn: Introduction to Mathematical Logic, 2nd ed. Van-Nostrand, London, 1979.
8. L. Zhongwan: Mathematical Logic for Computer Science, World Scientific, Singapore, 1989.
9. Gunter M. Ziegler and Martin Aigner: Proofs from The Book, Fourth Edition, Springer-Verlag, 2010
Other lecture notes and books will be added as and when required.

Some Interesting books:
1. Apostolos Doxiadis and Christos H Papadimitriou: Logicomix : an epic search for truth
2. Douglas Hofstadter: Godel, Escher, Bach: The eternal Golden Braid