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:

Course Outcomes

Affinity Mapping

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.

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.