SGBAU SY AI & DS syllabus

SGBAU · Second Year B.E. Artificial Intelligence and Data Science · NEP 2020

Discrete Structure and Graph Theory

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

  1. Unit 1: The Foundations: Logic and Proofs

    7 hours

    Propositions, truth tables and compound propositions, logical operators and bit operations, logical equivalences, normal forms and De Morgan's laws, satisfiability; predicates and quantifiers with restricted domains and precedence; rules of inference for propositional logic.

    Examined in the 60-mark end-semester paper

    • Propositions and truth tables
    • Logical equivalences and normal forms
    • Predicates and quantifiers
    • Nested quantifiers
    • Rules of inference and valid arguments
  2. Unit 2: Sets, Functions and Relations

    7 hours

    Sets, Venn diagrams, subsets, power sets and Cartesian products, set operations; functions, inverses, composition and partial functions, sequences and summations, countable and uncountable sets; relations and their properties, matrix representation, closures and equivalence relations.

    Examined in the 60-mark end-semester paper

  3. Unit 3: Algebraic Structures

    7 hours

    Algebraic systems and their properties; semigroups and monoids, their homomorphisms and substructures; groups, subgroups and homomorphisms, cosets and Lagrange's theorem, normal subgroups; systems with two binary operations; group codes, error correction and Hamming distance.

    Examined in the 60-mark end-semester paper

    • Binary operations and algebraic systems
    • Semigroups, monoids and groups
    • Cyclic and permutation groups
    • Normal subgroups and quotient structures
    • Rings, integral domains and fields
  4. Unit 4: Boolean Algebra

    7 hours

    Lattices and Boolean algebra; Boolean functions and their representation as sum-of-products and product-of-sums expansions; functional completeness, logic gates and combinations of gates; minimisation of circuits with Karnaugh maps.

    Examined in the 60-mark end-semester paper

    • Partial orders and Hasse diagrams
    • Boolean algebra
    • K-map minimisation
  5. Unit 5: Trees

    7 hours

    Rooted and ordered rooted trees, trees as models and their properties; applications — binary search trees, decision trees, prefix codes and Huffman coding, game trees; preorder, inorder and postorder traversal; spanning trees and minimum spanning trees.

    Examined in the 60-mark end-semester paper

  6. Unit 6: Graphs

    7 hours

    Graph models and terminology, special simple and bipartite graphs, matchings, new graphs from old; adjacency and incidence matrices, isomorphism; paths and connectedness, counting paths; Euler and Hamilton paths and circuits; planar graphs, Euler's formula and Kuratowski's theorem; graph colouring.

    Examined in the 60-mark end-semester paper

    • Graphs, subgraphs and degree
    • Special graphs and bipartite graphs
    • Matrix representations of graphs
    • Graph isomorphism and planar graphs
    • Euler and Hamiltonian paths
    • Graph colouring and matching

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