MA7860 Discrete Mathematics
Course Details
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.
Course References:
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.