MA7860 Discrete Mathematics

Course contents:

Combinatorics: Pigeonhole Principle, Principle of Inclusion and Exclusion, Catalan Number Stirling Number, Ramsey Number.

 

Graph Theory:Matching, Connectivity, Planar Graphs, Hamiltonian Graphs, Graph coloring.

 

Logic and Set Theory: First Order Logic, Quantifier Rules, Compactness Theorem, Schroder-Burnstein Theorem, Cantor's Diagonalization, Axiom of Choice, Continum Hypothesis.

 

Computability and Complixity:C...omputable Functions, Halting Problem, Post Correspondence Theorem, Rice Theorem. P, NP and co-NP, NP-completeness, Cooks Theorem, SAT, Knapsac Problem, Vertex Cover, Independent set, TSP.

 

Text Books:

1.      PJ Carneron, Combinatorits: Topics, Techniques.Algorithms, Cambridge University Press, 1994.

2.      G Chartand and L Lesniak, Graphs and Digraphs, Chapman & HaII/CRC 2004. .

3.      A Singh, Logic for Computer Science, PHI 2004.

4.      A Singh, Elements of Compuation Theory, Texts in Computer Science, Springer, 2009.

 

Reference:

1.      P R Halmos, Naive Set Theory, Van Nostrand, Princeton, 1960.

2.      G Ausiello P Crescenzi G Gambosi V Kann A Maechetti-Spaccamela and M Protasi, Complexity and Approximation, Springer, 1999.

3.      Kamala Krithivasan and R.Rama, Introduction to Automata Theory, Formal Languages and Computation, Pearson Education, 2009.