Course

Unit 1

Logic, Mathematical Reasoning and Counting: Logic, Prepositional Equivalence, Predicate and Quantifiers, Theorem Proving, Functions, Mathematical Induction. Recursive Definitions, Recursive Algorithms, Basics of Counting, Pigeonhole Principle, Permutation and Combinations. (Sections: 1.1 -1.4, 1.6 -1.8, 2.3, 5.1 – 5.4, 6.1 – 6.3 and 5.5)

Unit 2

Relations and Their Properties: Representing Relations, Closure of Relations, Partial Ordering, Equivalence Relations and partitions. (Sections: 9.1, 9.3 – 9.6)Advanced Counting Techniques and Relations: Recurrence Relations, Solving Recurrence Relations, Generating Functions, Solutions of Homogeneous Recurrence Relations, Divide and Conquer Relations, Inclusion-Exclusion. (Sections: 8.1 – 8.6)

Unit 3

Graph Theory: Introduction to Graphs, Graph Operations, Graph and Matrices, Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Shortest Path Problem, Planar Graph, Graph Colorings and Chromatic Polynomials. (Sections: 10.1 – 10.8).

Text Books / References

Text Books:

1. Kenneth H. Rosen, “Discrete Mathematics and its Applications”, Tata McGraw- Hill Publishing Company Limited, New Delhi, Eighth Edition, 2019.

References:

1. P. Grimaldi, “Discrete and Combinatorial Mathematics”, Pearson Education, Fifth Edition, 2007.
2. Thomas Koshy, “Discrete Mathematics with Applications”, Academic Press, 2005.
3. Liu, “Elements of Discrete Mathematics”, Tata McGraw- Hill Publishing Company Limited, 200

Course Outcomes:

• CO1: To understand the basic concepts of Mathematical reasoning, set and functions.
• CO2: To understand various counting techniques and principle of inclusion and exclusions.
• CO3: Understand the concepts of various types of relations, partial ordering and equivalence relations.
• CO4: Apply the concepts of generating functions to solve the recurrence relations.
• CO5: Familiarise the fundamental concepts of graph theory and shortest path algorithm.

CO-PO Mapping