COURSE SUMMARY
Course Title:
Discrete Mathematics
Course Code:
19MAT115
Year Taught:
2019
Semester:
2
Type:
Foundation Core
Degree:
School:
School of Engineering
Campus:
Bengaluru
Chennai
Coimbatore
Amritapuri

'Discrete Mathematics' is a course offered in the second semester of B. Tech. programs at the School of Engineering, Amrita Vishwa Vidyapeetham.

### Course Outcomes

 CO1 Understand the basic concepts of Mathematical reasoning and basic counting techniques. Also understand the different types of proves like mathematical induction. CO2 Understand the concepts of various types of relations, partial ordering and equivalence relations. CO3 Apply the concepts of generating functions to solve the recurrence relations. CO4 Apply the concepts of divide and conquer method and principle of inclusion and exclusion to solve some simple algorithms in discrete mathematics. CO5 Understand various definitions in graph theory and study their properties. Also, understand the shortest path problem and apply to a network.

Affinity Mapping

 Cos PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 CO1 3 2 1 CO2 3 3 2 CO3 3 3 2 CO4 3 2 1 CO5 2 3 2

Course Evaluation Pattern

• Test-1 -15 marks (two hour test)
• CA - 20 marks (Quizzes / assignments / lab practice)
• Test – 2- 15 marks (two-hour test)
• End semester- 50 marks.
• Total - 100 marks.

Supplementary exam for this course will be conducted as a three-hour test for 50 marks.

#### SYLLABUS

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)

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)

Number Theory: Divisibility and Factorization. Congruences. Simultaneous linear congruences, Chinese Remainder Theorem. Wilson's Theorem, Fermat's Theorem, pseudoprimes and Carmichael numbers, Euler's Theorem. Arithmetic functions and Quadratic residues:

#### TEXT BOOKS / REFERENCES

Text Book

• Kenneth H. Rosen, “Discrete Mathematics and its Applications”, Tata McGraw- Hill Publishing Company Limited, New Delhi, Sixth Edition, 2007.
• James Strayer, Elementary Number Theory, Waveland Press, 2002.

Reference Book(s)

• 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.