Course Outcomes:
• Solve problems related to fundamentals of mathematical logic.
• Model and solve practical problems using graph-theoretic techniques.
• Solve problems related to counting and combinatorics
Course Details:
Module 1: Review of Sets, Operations, Principles of Inclusion and Exclusion. Functions, relations, Equivalence relations. Countable and uncountable sets. Review of the Pigeonhole principle.
Module 2: Introduction to Propositional Logic, Equivalence, and Implications. Truth tables, De Morgan’s Law, Quantifiers, Inference, and Proofs. Introduction to First-Order Logic, Syntax, and Semantics, Soundness, and Completeness.
Module 3: Mathematical Induction, Recursions, First order linear recurrence, Geometric series, Recursion trees and growth rates of solutions to recurrences, Master Theorem. Generating Functions.
Module 4: Introduction to counting, sum and product principles, counting subsets. Binomial coefficients and Pascal’s triangles. Polya’s theory of counting (optional).
Module 5: Arithmetic Algorithms: Computing GCD, primality testing, RSA.
Module 6: Graph Theory: Graphs, representations, connectivity, cycles, trees, Spanning tree of a graph, Algorithms to find minimum spanning trees. Eulerian Cycle and Hamiltonian paths, independence number and clique number, chromatic number, Dominating Sets, and Covering Sets. Planar Graphs. Directed Graphs and tournaments.
Module 7: Probabilistic tools, Tail Bounds, and Applications.
Module 8: Linear Algebraic tools in Combinatorics.
References
• J. Gallier, Logic for Computer Science: Foundations of Automatic Theorem Proving, Wiley. • Kenneth Rosen. Discrete Mathematics and Its Applications, 7th Edition, McGraw Hill Publishing Co., 2012.
• Ken Bogart. Discrete Mathematics for Computer Science. available
at https://www.kth.se/social/files/557ec6b0f27654
• J. L. Mott, A. Kandel and T. P. Baker: Discrete Mathematics for Computer Scientists, Reston, Virginia, 1983
• J. A. Bondy and U. S. R. Murty: Graph Theory with Applications, Macmillan Press, London, 1976. • F. S. Roberts: Applied Combinatorics, Prentice Hall, Englewood Cliffs, NJ, 1984