Discrete Mathematical Structures - I

Instruction: 3 Periods & 1 Tut /week

Univ. Exam : 3 Hours

Sessional Marks: 30

Univ-Exam-Marks:70

Introduction: Sets-Operations on sets-relations-functions-Proof methods and problem solving strategies-Fundamentals of Logic- Logical inferences-Methods of proof of an implication-First Order logic and Other Proof methods-Rules of inference for quantified Propositions-Mathematical Induction

Elementary Combinatorics: Basics of Counting- Combinations and Permutations-Their Enumeration with and without repetition-Binomial coefficients-Binomial and Multinomial Theorems-The Principle of Inclusion-Exclusion.

Recurrence Relations: Generating Functions of Sequences-Calculating their Coefficients-Recurrence relations-Solving recurrence relations-Method of characteristic Roots- Non-homogeneous Recurrence relations and their solutions

Relations and Digraphs: Relations and Directed Graphs-Special Properties of Binary relations- Equivalence Relations-Ordering Relations-Lattices and Enumeration- Operations on relations-Paths and Closures-Directed Graphs and Adjacency matrices- Applications of sorting, searching and topological sorting.

Graphs: Basic concepts-Isomorphism-subgraphs-Planar Graphs-Euler’s formula- Multigraphs and Euler circuits-Hamiltonian graphs-Chromatic numbers-Four color theorem.

Trees: Trees and their properties-Trees as graphs-spanning trees-Directed trees-Binary trees-Their traversals-Arithmetic and Boolean expressions as trees- height balanced trees.

Text Book:

"Discrete Mathematics for computer scientists & Mathematicians" by Joe L. Mott, Abraham Kandel & T. P. Baker, Prentice Hall of India Ltd, New Delhi

Reference Books:

1) "Discrete mathematics and its applications" by Keneth. H. Rosen, , Tata McGraw- Hill Publishing Company, New Delhi

2) "Discrete mathematics" by Richard Johnsonbaug, Pearson Education, New Delhi