Mumbai University SE Computer syllabus

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.

All notes for this subject
  1. Module 1: Crisp Set Theory and Logic

    7 hours

    Sets, 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

  2. Module 2: Mathematical Relations

    8 hours

    Relations, 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

  3. Module 3: Functions

    3 hours

    Injective, 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

  4. Module 4: Counting

    5 hours

    The 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

  5. Module 5: Algebraic Structures

    7 hours

    Semigroups, monoids, groups, subgroups, abelian and cyclic groups; rings.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  6. Module 6: Graph Theory

    8 hours

    Types 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

Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.