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

## About the course

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.

- Fred Roberts and Barry Tesman: Applied Combinatorics, Second Edition, CRC Press, 2009.
- J. H. van Lint and R. M. Wilson: A Course in Combinatorics, Second Edition, Cambridge University Press, 2001.
- C. L. Liu: Elements of Discrete Mathematics, 2nd ed., McGraw Hill, New Delhi, 1985.
- R. A. Brualdi: Introductory Combinatorics, North-Holland, New York, 1977.
- Douglas B. West: Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.
- J. A. Bondy and U. S. R. Murty: Graph Theory with Applications, Macmillan Press, London, 1976.
- E. Mendelsohn: Introduction to Mathematical Logic, 2nd ed. Van-Nostrand, London, 1979.
- L. Zhongwan: Mathematical Logic for Computer Science, World Scientific, Singapore, 1989.
- 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:
- Apostolos Doxiadis and Christos H Papadimitriou: Logicomix : an epic search for truth
- Douglas Hofstadter: Godel, Escher, Bach: The eternal Golden Braid

## About Scribing

Each class note will be scribed by two students as will be decided in class. Please use this template for scribing.
Please do not forget to add references.
## Lecture Notes (Partial List)

Please mail me if you find mistakes in the scribes.
- Basics of counting
- Principle of Inclusion and Exclusion
- Generating Functions
- Recurrence Relations
- Recurrence Relations (contd)
- Catalan Numbers
- Graph Theory (Basics)
- Cycles, Paths