KBCNMU · Second Year B.E. Artificial Intelligence & Data Science · NEP 2020
Discrete Mathematics
AIDS-301 · Semester III · 3 credits · ISE 40 + ESE 60
Unit 1: Set, Relation and Function
9 hoursOperations and laws of sets, Cartesian products, Cantor's diagonal argument, the power set theorem and the Schröder–Bernstein theorem; binary, partial-order and equivalence relations; bijective, inverse and composite functions.
Examined in the 60-mark end-semester paper
- Sets, set operations and identities
- Cardinality of sets
- Relations and their properties
- Partial orders and Hasse diagrams
- Equivalence relations and partitions
- Functions: injective, surjective and bijective
- Composition, inverse and recursive functions
Unit 2: Mathematical Induction and Counting
9 hoursThe well-ordering principle, recursive definitions and induction; the division algorithm, primes, GCD by the Euclidean algorithm and the fundamental theorem of arithmetic; inclusion–exclusion, the pigeonhole principle, permutations and combinations; number systems and conversion.
Examined in the 60-mark end-semester paper
- Mathematical induction
- Division algorithm, GCD and the Euclidean algorithm
- Primes and the fundamental theorem of arithmetic
- Inclusion–exclusion principle
- Pigeonhole principle
- Permutations and combinations
- Number systems and conversions
Unit 3: Propositional Logic
9 hoursSyntax and semantics, validity and satisfiability, connectives and truth tables; logical equivalence, implication, rules of inference and quantifiers; proof methods — direct, by contradiction, by contraposition, and of necessity and sufficiency.
Examined in the 60-mark end-semester paper
- Propositions and truth tables
- Logical equivalences and normal forms
- Rules of inference and valid arguments
- Predicates and quantifiers
- Methods of proof
Unit 4: Algebraic Structures and Morphism
9 hoursAlgebraic structures with one binary operation — semigroups, monoids and groups — and with two — rings, integral domains and fields; Boolean algebra and Boolean rings, duality, Boolean functions in disjunctive and conjunctive normal form.
Examined in the 60-mark end-semester paper
- Binary operations and algebraic systems
- Semigroups, monoids and groups
- Rings, integral domains and fields
- Boolean algebra
Unit 5: Graphs and Trees
9 hoursGraph properties — degree, connectivity, paths, cycles, subgraphs and isomorphism; Eulerian and Hamiltonian walks, colouring and planar graphs, perfect graphs; Dijkstra's shortest path; rooted and weighted trees, prefix codes, and Kruskal's and Prim's minimum spanning trees.
Examined in the 60-mark end-semester paper
- Graphs, subgraphs and degree
- Graph isomorphism and planar graphs
- Euler and Hamiltonian paths
- Graph colouring and matching
- Shortest paths: Dijkstra and Floyd–Warshall
- Trees and their properties
- Prefix codes and Huffman coding
- Prim's and Kruskal's algorithms
Unit contents are summarised from the official KBCNMU syllabus . AiCanCode.org is not affiliated with Kavayitri Bahinabai Chaudhari North Maharashtra University (KBCNMU).