Descrete Mathematical Structures-I

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.