DBATU · Second Year B.Tech Information Technology · NEP 2020
Discrete Mathematics
25AF1246PC404 · Semester IV · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60
Unit 1: Sets and Logic
7 hoursSet operations, power sets, partitions and cardinality; the inclusion–exclusion principle; propositional and predicate logic, quantifiers; rules of inference and proof strategies; applications in web search and bitwise operations.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Sets, power sets and partitions
- Inclusion–exclusion principle
- Propositional logic
- Predicate logic and quantifiers
- Rules of inference and proof strategies
Unit 2: Induction, Recursion and Functions
7 hoursMathematical and strong induction; recursive definitions and algorithms; injective, surjective and bijective functions; composition, identity, inverse and recursive functions; job scheduling.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Mathematical and strong induction
- Recursive definitions and algorithms
- Types of functions
- Composition and inverse of functions
Unit 3: Counting and Recurrence
7 hoursPermutations and combinations with and without repetition; binomial coefficients; the pigeonhole principle; generating permutations; solving recurrence relations.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Permutations and combinations
- Binomial coefficients
- Pigeonhole principle
- Solving recurrence relations
Unit 4: Relations and Algebraic Structures
7 hoursBinary relations and closures; equivalence relations and partial orders; Warshall's algorithm; n-ary relations and databases; groups, monoids, rings and fields; codes, homomorphism, Fermat's theorem and polynomial rings.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Relations and their properties
- Closures and Warshall's algorithm
- Equivalence relations and partial orders
- Groups, monoids and semigroups
- Rings and fields
- Group codes and homomorphism
Unit 5: Graph Theory
7 hoursTypes of graph, paths and circuits; Euler and Hamiltonian paths; graph colouring, independent sets and planar graphs; trees, spanning trees and cut sets; Kruskal's and Prim's algorithms; TSP and shortest paths.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Graphs, paths and circuits
- Euler and Hamiltonian paths
- Graph colouring and planar graphs
- Trees, spanning trees and cut sets
- Minimum spanning trees and shortest paths
Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).