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
Unit 1: The Foundations: Logic and Proofs
7 hoursPropositions, 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
Unit 2: Sets, Functions and Relations
7 hoursSets, 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
- Sets, set operations and identities
- Cardinality of sets
- Functions: injective, surjective and bijective
- Relations and their properties
- Closures of relations
- Equivalence relations and partitions
Unit 3: Algebraic Structures
7 hoursAlgebraic 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
Unit 4: Boolean Algebra
7 hoursLattices 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
Unit 5: Trees
7 hoursRooted 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
- Trees and their properties
- Binary search trees
- Prefix codes and Huffman coding
- Binary tree traversals
- Spanning trees and minimal spanning trees
Unit 6: Graphs
7 hoursGraph 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).