Course

Unit I

Logic, Mathematical Reasoning and Counting: Logic, Prepositional Equivalence, Predicate and Quantifiers, Theorem Proving. Recursive Definitions, Recursive Algorithms, Basics of Counting, Pigeonhole Principle, Permutation and Combinations.

Unit II

Relations and Their Properties: Representing Relations, Closure of Relations, Partial Ordering, Equivalence Relations and partitions.

Advanced Counting Techniques and Relations: Recurrence Relations, Solving Recurrence Relations, Generating Functions, Solutions of Homogeneous Recurrence Relations, Divide and Conquer Relations, Inclusion-Exclusion.

Unit III

Graph Theory: Graphs and Sub graphs, isomorphism, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithm. Euler and Hamilton Graphs: Euler graphs, Euler’s theorem. Fleury’s algorithm for Eulerian trails. Hamilton cycles, Chinese-postman problem, approximate solutions of traveling salesman problem. Closest neighbour algorithm.

Lab Practice Problems

Verifications of logical statements, truth table, tautology. Recursive algorithms. Graph problems, degree, shortest path algorithm, Euler’s algorithm and closest neighbour algorithm.

Course Objectives

• Understand the logic and various functions.
• Understand the basic concept of combinatorics
• Understand the concepts of recurrence relations and their applications.
• Understand the concepts of equivalence and partial order relations.
• Understand various definitions and theorems on graph theory.

Course Outcomes

CO1: To understand the basic concepts of Mathematical reasoning and basic counting techniques.
CO2: To understand the recursive functions and apply the concepts of generating functions to solve the recurrence relations.
CO3: Apply the concepts of divide and conquer method and principle of inclusion and exclusion to solve some simple algorithms in discrete mathematics
CO4: To understand the concepts of various types of relations, partial ordering and equivalence relations.
CO5: To understand the basic concepts of graph theory and apply to shortest path problems.

CO-PO Mapping

Evaluation Pattern: 70:30

Textbook(s)

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

Lab Experiments:

1. Program to construct truth tables for some compound propositions
2. Program to check the validity for all rules of inference using truth tables
3. Program to check whether a given function is one-one and / or onto
4. Programs on mathematical induction
5. Programs involving recursion-i : factorial, power, gcd, modular exponentiation
6. Programs involving recursion-ii : fibonnaci series, towers of hanoi
7. Program to check whether a given number is prime
8. Programs involving modelling of recurrence relations
9. Program to check different properties of relations- reflexivity, symmetry, antisymmetry, transitivity
10. Program to find transitive closure using warshalls algorithm
11. Programs on divisibility and factorization
12. Program on fundamental theorem of airthmetic
13. Program on chinese remainder theorem

iel and Pauley E. Steven. “Technical Report Writing Today”, VIII Edition (Indian Adaptation).New Delhi: Biztantra, 2004.

Michael Swan. “Practical English Usage”, Oxford University Press, 2000.