SGBAU SY IT syllabus

SGBAU · Second Year B.E. Information Technology · NEP 2020

Discrete Structure & Graph Theory

3IT200PC · Semester III · 3 credits · IE 40 + ESE 60

  1. Unit 1: Mathematical Logic

    7 hours

    Statements, notation and connectives; normal forms; the theory of inference for the statement calculus; predicate calculus and its inference theory.

    Examined in the 60-mark end-semester paper

    • Propositional logic
    • Logical equivalences and normal forms
    • Rules of inference and proof strategies
    • Predicate logic and quantifiers
  2. Unit 2: Set Theory

    7 hours

    Basic concepts of set theory and the representation of discrete structures; relations and ordering; functions; recursion.

    Examined in the 60-mark end-semester paper

    • Sets, power sets and partitions
    • Relations and their properties
    • Equivalence relations and partial orders
    • Types of functions
    • Recursive definitions and algorithms
  3. Unit 3: Algebraic Structures

    7 hours

    Algebraic systems, semigroups, monoids and groups; grammars and languages; Polish expressions and their compilation; residue arithmetic and its application to computers.

    Examined in the 60-mark end-semester paper

  4. Unit 4: Lattice & Boolean Algebra

    7 hours

    Lattices as partially ordered sets; Boolean algebra and Boolean functions, their representation and minimisation.

    Examined in the 60-mark end-semester paper

  5. Unit 5: Graph Theory

    7 hours

    Basic concepts of graph theory; paths, reachability and connectedness; matrix representation, storage and manipulation of graphs; graph colouring.

    Examined in the 60-mark end-semester paper

    • Graphs, paths and circuits
    • Closures and Warshall's algorithm
    • Graph representation, BFS and DFS
    • Graph colouring and planar graphs
  6. Unit 6: Trees

    7 hours

    Trees and tree searching; minimal spanning trees; simple precedence grammars; rooted and expression trees; B-trees; distance between spanning trees of a graph.

    Examined in the 60-mark end-semester paper

    • Trees, spanning trees and cut sets
    • Minimum spanning trees and shortest paths
    • Binary tree traversals
    • B-trees and B+ trees

Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).