KBCNMU · Second Year B.E. Computer Engineering · NEP 2020
Discrete Mathematics
CS-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 and Schroeder–Bernstein theorems; binary, partial-order and equivalence relations; bijective, inverse and composite functions.
Examined in the 60-mark end-semester paper
Unit 2: Mathematical Induction and Counting
9 hoursThe well-ordering principle, recursive definitions, the division algorithm, primes, GCD by Euclid's algorithm and the fundamental theorem of arithmetic; inclusion–exclusion, the pigeonhole principle, permutations and combinations; number systems and their conversion.
Examined in the 60-mark end-semester paper
- Mathematical induction
- Number theory: Fermat's and Euler's theorems and Euclid's algorithm
- Inclusion–exclusion principle
- Pigeonhole principle
- Permutations and combinations
- Number systems and conversions
Unit 3: Propositional Logic and Proof Techniques
9 hoursSyntax, semantics, validity and satisfiability, connectives and truth tables, the laws of logic, logical implication, rules of inference and quantifiers; forward proof, proof by contradiction and contraposition, necessity and sufficiency.
Examined in the 60-mark end-semester paper
- Propositional logic and equivalences
- Predicate logic and quantifiers
- Rules of inference and valid arguments
- 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
- Groups, semigroups and monoids
- Rings, integral domains and fields
- Boolean algebra and Boolean rings
- SOP and POS forms
Unit 5: Graphs and Trees
9 hoursGraphs and their properties, degree, connectivity, paths and cycles, isomorphism, Eulerian and Hamiltonian walks, colouring and planar graphs, Dijkstra's algorithm; rooted and weighted trees, prefix codes, Kruskal's and Prim's minimum spanning trees.
Examined in the 60-mark end-semester paper
Unit contents are summarised from the official KBCNMU syllabus . AiCanCode.org is not affiliated with Kavayitri Bahinabai Chaudhari North Maharashtra University (KBCNMU).