DBATU · Second Year B.Tech Computer Engineering · NEP 2020
Discrete Mathematics
25AF1245PC303 · Semester III · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60
Unit 1: Propositional Logic, Predicates and Rules of Inference
9 hoursPropositions, truth tables and logical equivalences; normal forms; predicates, quantifiers and nested quantifiers; translating English into logic; rules of inference, resolution and fallacies.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Propositional logic and equivalences
- Predicate logic and quantifiers
- Nested quantifiers
- Translating English into logic
- Rules of inference and valid arguments
Unit 2: Sets, Functions and Relations
9 hoursSets, power sets, Cartesian products, identities and cardinality; injective, surjective, bijective, inverse and composite functions; relations, their representation and closures; equivalence relations and partitions; partial orders, Hasse diagrams and topological sort.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Set theory and set operations
- Countable and uncountable sets
- Functions: injective, surjective and bijective
- Composition, inverse and recursive functions
- Relations and their properties
- Representing relations: matrices and digraphs
- Equivalence relations and partitions
- Partial orders, Hasse diagrams and lattices
Unit 3: Combinatorics
6 hoursApplications of recurrence relations; solving linear recurrence relations.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Recurrence relations and their solution
- Applications of recurrence relations
Unit 4: Graphs and Trees
7 hoursSpecial simple and bipartite graphs; shortest paths; Euler and Hamiltonian paths; isomorphism; planar graphs, connectivity, matching and colouring; prefix codes and Huffman coding; spanning trees, cut sets and Kruskal's and Prim's algorithms.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Graph terminology and special graphs
- Graph representation and isomorphism
- Euler and Hamilton paths
- Planar graphs and graph colouring
- Dijkstra's shortest-path algorithm
- Prefix codes and Huffman coding
- Minimum spanning trees
- Cut sets and cut vertices
Unit 5: Algebraic Structures and Morphism
5 hoursSemigroups, monoids and groups; congruence relations and quotient structures; cyclic and permutation groups, subgroups and normal subgroups; rings, integral domains and fields; Boolean algebra and Boolean rings.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Groups, semigroups and monoids
- Subgroups, abelian and cyclic groups
- Congruence relations and quotient structures
- Rings, integral domains and fields
- Boolean algebra and Boolean rings
Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).