Discrete Mathematical Structures – I Syllabus
Periods/week : 3 Periods & 1 Tut /week. Ses. : 30 Exam : 70 Examination (Practical): 3hrs. Credits: 4
- 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.
“Discrete Mathematics for computer scientists & Mathematicians” by Joe L. Mott, Abraham Kandel & T. P. Baker, Prentice Hall of India Ltd, New Delhi
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