COURSE SUMMARY
Course Title:
Discrete Mathematics
Course Code:
15MAT201
Year Taught:
2015
2016
2017
2018
Semester:
3
Type:
Foundation Core
Degree:
School:
School of Engineering
Campus:
Bengaluru
Chennai
Coimbatore
Amritapuri

'Discrete Mathematics' is a course offered in the third semester of B. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.

#### SYLLABUS

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.3, 1.5 -1.7, 2.3, 4.1 - 4.4, 5.1 - 5.3 and 5.5)

Unit 2

Relations and Their Properties: Representing Relations, Closure of Relations, Partial Ordering, Equivalence Relations and partitions. (Sections: 7.1, 7.3 - 7.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: 6.1 - 6.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: 8.1 - 8.8)

#### TEXTBOOK

• Kenneth H. Rosen, “Discrete Mathematics and its Applications”, Tata McGraw- Hill Publishing Company Limited, New Delhi, Sixth Edition, 2007.

#### REFERENCES

• R. P. Grimaldi, “Discrete and Combinatorial Mathematics”, Pearson Education, Fifth Edition, 2007.
• Thomas Koshy, “Discrete Mathematics with Applications”, Academic Press, 2005.
• Liu, “Elements of Discrete Mathematics”, Tata McGraw Hill Publishing Company Limited, 2004.