Syllabus Discrete Mathematics (210241) Credit Scheme Examination Scheme and Marks 03 Mid_Semester (TH) : 30 Marks End_Semester (TH) : 70 Marks Unit I Set Theory and Logic Introduction and significance of Discrete Mathematics, Sets - Naïve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Set Operations, Cardinality of set, Principle of inclusion and exclusion. Types of Sets - Bounded and Unbounded Sets, Diagonalization Argument, Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets, Power set, Propositional Logic - logic, Propositional Equivalences, Application of Propositional Logic - Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction. (Chapter - 1) Unit II Relations and Functions Relations and their Properties, n-ary relations and their applications, Representing relations, Closures of relations, Equivalence relations, Partial orderings, Partitions, Hasse diagram, Lattices, Chains and Anti-Chains, Transitive closure and Warshall’s algorithm. Functions - Surjective, Injective and Bijective functions, Identity function, Partial function, Invertible function, Constant function, Inverse functions and Compositions of functions, The Pigeonhole Principle. (Chapter - 2) Unit III Counting Principles The Basics of Counting, rule of Sum and Product, Permutations and Combinations, Binomial Coefficients and Identities, Generalized Permutations and Combinations, Algorithms for generating Permutations and Combinations. (Chapter - 3) Unit IV Graph Theory Graph Terminology and Special Types of Graphs, Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, the handshaking lemma, Single source shortest path-Dijkstra's Algorithm, Planar Graphs, Graph Colouring. (Chapter - 4) Unit V Trees Introduction, properties of trees, Binary search tree, tree traversal, decision tree, prefix codes and Huffman coding, cut sets, Spanning Trees and Minimum Spanning Tree, Kruskal’s and Prim’s algorithms, The Max flow - Min Cut Theorem (Transport network). (Chapter - 5) Unit VI Algebraic Structures and Coding Theory The structure of algebra, Algebraic Systems, Semi Groups, Monoids, Groups, Homomorphism and Normal Subgroups, and Congruence relations, Rings, Integral Domains and Fields, Coding theory, Polynomial Rings and polynomial Codes, Galois Theory - Field Theory and Group Theory. (Chapter - 6)
