Discrete Mathematics syllabus

Introduction and significance of Discrete Mathematics, Propositional Logic-: logic, Propositional Equivalences, Application of Propositional Logic- Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction. Sets: Naive 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.

Case study: Know about the great philosophers- Georg Cantor, Richard Dedekind and Aristotle. Design a recommendation system using logical propositions and predicates to filter movies based on user preferences.

Introduction to Relations and their Properties Representation of Relations using Matrices and Digraphs Equivalence relations, Partial orderings, Partitions, Hasse diagram, Lattices, Chains and Anti- Chains, Transitive closure and Warshall‘s algorithm. Functions: Types of Functions (Injective, Surjective, Bijective) , Composition and Inverse of Functions , Recursive Functions and Applications in Algorithms , Counting Functions and Growth of Functions.

Introduction to Trees and Properties ,Binary Trees and Binary Search Trees (BST) ,Tree Traversal Techniques: Preorder, Inorder, Postorder , Huffman Trees and Data Compression Algorithms ,Decision Trees and their Applications in Machine Learning , Applications of Trees in File Systems, The Max flow- Min Cut Theorem in Transport network.

Introduction to Graphs: Types and Representation ,Graph Traversals: BFS and DFS ,Connected Components and Path finding Algorithms, Eulerian and Hamiltonian Paths and Circuits , Planar Graphs and Graph Coloring, Dijkstra’s Algorithm for Shortest Paths , Spanning Trees and Minimum Spanning Tree Algorithms (Prim’s and Kruskal’s)

Case study : Model a social media platform using directed graphs to represent relationships such as “follower” or “friend.” Three utility problem, Web Graph, Google map

Basic Counting Techniques: Addition and Multiplication Principles , Permutations and Combinations, Binomial Coefficients and Pascal’s Triangle, Pigeonhole Principle and its Applications , Inclusion- Exclusion Principle, Generating Functions for Counting Problems. The structure of algebra, Algebraic Systems, Semi Groups, Monoids, Groups, Homomorphism and Normal Subgroups and Congruence relations, Rings, Integral Domains and Fields.