Mumbai University · Second Year Computer Engineering · NEP 2020
Discrete Structures and Graph Theory
2113112 · Semester III · 3 credits · Internal tests 40 + end-semester 60
End-semester paper (2 hours): Six questions of 15 marks; Q1 is compulsory and you answer four.
Module 1: Crisp Set Theory and Logic
7 hoursSets, subsets, operations, representation and laws; propositional and predicate logic and quantifiers; direct proof, contradiction, deduction, cases, exhaustion, counterexample and induction.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Set theory and set operations
- Propositional logic and equivalences
- Predicate logic and quantifiers
- Methods of proof
- Mathematical induction
Module 2: Mathematical Relations
8 hoursRelations, their representation and properties; equivalence relations and classes; closures and Warshall's algorithm; partial orders, posets and Hasse diagrams; chains and antichains; lattices, their types and sublattices.
Examined in one of the two internal tests and in the 60-mark end-semester paper
Module 3: Functions
3 hoursInjective, surjective and bijective functions; composition and inverse functions; applications.
Examined in one of the two internal tests and in the 60-mark end-semester paper
Module 4: Counting
5 hoursThe pigeonhole and inclusion–exclusion principles; recurrence relations and their solution.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Pigeonhole principle
- Inclusion–exclusion principle
- Recurrence relations and their solution
Module 5: Algebraic Structures
7 hoursSemigroups, monoids, groups, subgroups, abelian and cyclic groups; rings.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Groups, semigroups and monoids
- Subgroups, abelian and cyclic groups
- Rings, integral domains and fields
Module 6: Graph Theory
8 hoursTypes and representation of graphs; subgraphs and graph operations; walks, paths, circuits and connectivity; homomorphism and isomorphism; Euler and Hamiltonian graphs; planar graphs; cut sets and cut vertices; applications.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Graph terminology and special graphs
- Graph representation and isomorphism
- Euler and Hamilton paths
- Planar graphs and graph colouring
- Cut sets and cut vertices
Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.