Instructor: Dr. Nilanjan Datta

Course Objective:

The primary objective of the course is that students should learn a particular set of mathematical facts and how to apply them. In particular, this course should be able to teach the students how to think logically and mathematically. The students will be able to understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments which serves as the foundation for the subsequent discussions of methods of proof. They should be able to perform combinatorial analysis to solve counting problems and analyze algorithms, not on applying formulae. The students would be able to work with discrete structures, such as sets, permutations, relations, graphs, which are the abstract mathematical structures used to represent discrete objects and relationships between these objects. They will also be able to perform the mathematical portions of various algorithms, which include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it. Discrete mathematics has many applications to computer science and data networking in this text, as well as applications to such diverse areas as chemistry, biology, linguistics, geography, business, and the Internet. Students of this course will learn to solve such applications by modeling them with discrete mathematics.

Detailed Syllabus:

1. The Foundations – Logic and Proofs: Propositional logic, Predicates and Quantifiers, Rules of Inference, Proof methods and strategies.

2. Combinatorics: Sets, Functions, Relations, Equivalence relation, Partitions, PO Set, Lattice; Basics of counting, Pigeon-hole principle, Permutation, Combination, Binomial and Multinomial Theorem, Generating permutation and combination, Inclusion-Exclusion and its application; Recurrence relation, Solving linear recurrence relation, Generating functions; Discrete Probability, Conditional probability, Bayes theorem, Random variable, Probability distribution functions, Basic Number theory, Divisibility, Congruence, GCD, Euclidean Algorithm, Extended Euclidean Algorithm, Chinese Remainder theorem, RSA.

3. Graph Theory: Graphs and di-graphs, Basic terminologies (clique, independent set, vertex cover, degree, regular, complement), Graph models, Isomorphism, Representation of graphs, Connectivity, Eulerian paths and circuits, Hamiltonian paths and circuits, Knight’s Tour; Graph traversal, Topological Sorting, Shortest path algorithms, Tree, Counting trees (Prufer Code), Minimal Spanning Trees, Planar graphs, Euler’s Formula, Kuratowski’s Theorem, Five-color Theorem, Bi-partite Matching, Halls Theorem, Stable Matching, Matching in any graph, Tutte’s Theorem, Coloring of graphs, Chromatic Number, Brooks Theorem, Vizing’s Theorem, Art Gallery Problem.

References:

[1] K. H. Rosen: Discrete Mathematics and Its Applications (8th Edition), McGraw Hill, 2019.

[2] N. L. Biggs: Discrete Mathematics, Clarendon Press, 1985.

[3] C. L. Liu: Elements of Discrete Mathematics, McGraw Hills, 1985.

[4] J. A. Bondy, U. S. R. Murty: Graph Theory, Graduate texts in mathematics 244, Springer, 2008.

[5] D. West: Introduction to Graph Theory, Prentice Hall, 2000.

[6] R. Diestel: Graph Theory, Graduate texts in mathematics 173, Springer-Verlag Berlin Heidelberg, 2017.


Classes:

  • Lecture 1 (Some Motivating Puzzles)
  • Lecture 2 (Propositional Logic, Interesting Applications)
  • Lecture 3 (Predicate, Quantifier, Rules of Inference)
  • Lecture 4 (Proof Methods and Proof Strategy, Common Mistakes in Proofs)
  • Lecture 5 (Sets, Relation, Equivalence Relation, POSET)
  • Lecture 6 (Function, Infinite Sets, Schroder-Bernstein Theorem)
  • Lecture 7 (Counting Rules, and their applications: Sum-Rule, Product Rule)
  • Lecture 8 (Counting Equivalent Problems, Principles of Inclusion-Exclusion, Pigeon-hole Principle)
  • Discussion on Assignment 1
  • Lecture 9 (Introduction to Graphs, Basic terminologies, Special types of graphs, Representation of graphs)

    24/09/2021: Discussion on Assignment 2 and Assignment 3

The board works are available here: [Class Notes].


Home Work / Assignments :

Model Questions for Examinations :