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.
  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

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.
  1. Basics of counting
  2. Principle of Inclusion and Exclusion
  3. Generating Functions
  4. Recurrence Relations
  5. Recurrence Relations (contd)
  6. Catalan Numbers
  7. Graph Theory (Basics)
  8. Cycles, Paths