Syllabus Discrete Mathematics - (214441) Credit Scheme : Examination Scheme : 03 01 Mid_Semester : 30 Marks End_Semester : 70 Marks Term Work : 25 Marks Unit I Sets And Propositions Sets : Sets, Combinations of Sets, Venn Diagram, Finite and Infinite Sets, Countable Sets, Multisets, Principle of Inclusion and Exclusion, Mathematical Induction. Propositions : Propositions, Logical Connectives, Conditional and Bi-conditional Propositions, Logical Equivalence, Validity of Arguments by using Truth Tables, Predicates and Quantifiers, Normal forms. Applications of Sets and Propositions. (Chpater - 1) Unit II Combinatorics And Discrete Probability Combinatorics : Rules of Sum and Product, Permutations, Combinations. Discrete Probability : Discrete Probability, Conditional Probability, Bayes Theorem, Information and Mutual Information, Applications of Combinatorics and Discrete Probability. (Chpater - 2) Unit III Graph Theory Graphs : Basic Terminologies, Multi-Graphs, Weighted Graphs, Sub Graphs, Isomorphic graphs, Complete Graphs, Regular Graphs, Bipartite Graphs, Operations on Graphs, Paths, Circuits, Hamiltonian and Eulerian graphs, Travelling Salesman Problem, Factors of Graphs, Planar Graphs, Graph Colouring. Trees : Tree Terminologies, Rooted Trees, Path Length in Rooted Trees, Prefix Codes, Spanning Trees, Fundamental Cut Sets and Circuits, Max flow –Min Cut Theorem (Transport Network). Applications of Graph Theory. (Chpater - 3) Unit IV Relations And Functions Relations : Properties of Binary Relations, Closure of Relations, Warshall’s Algorithm, Equivalence Relations, Partitions, Partial Ordering Relations, Lattices, Chains and Anti Chains. Functions : Functions, Composition of Functions, Invertible Functions, Pigeonhole Principle, Discrete Numeric Functions. Recurrence Relations : Recurrence Relation, Linear Recurrence Relations with Constant Coefficients, Total Solutions, Applications of Relations and Functions. (Chapter - 4) Unit V Introduction To Number Theory Divisibility of Integers : Properties of Divisibility, Division Algorithm, Greatest Common Divisor GCD and its Properties, Euclidean Algorithm, Extended Euclidean Algorithm, Prime Factorization Theorem, Congruence Relation, Modular Arithmetic, Euler Phi Function, Euler’s Theorem, Fermat's Little Theorem, Additive and Multiplicative Inverses, Chinese Remainder Theorem. (Chpater - 5) Unit VI Algebraic Structures Algebraic Structures : Introduction Semigroup, Monoid, Group, Abelian Group, Permutation Groups, Cosets, Normal Subgroup, Codes and Group Codes, Ring, Integral Domain, Field. Applications of Algebraic Structures. (Chpater - 6)