Course DEtails

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