SGBAU · Second Year B.E. Computer Engineering · NEP 2020
Discrete Structure and Graph Theory
3KE200PC · 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
- Propositional logic and equivalences
- Predicate logic 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
- Set theory and set operations
- Countable and uncountable sets
- Functions: injective, surjective and bijective
- Composition, inverse and recursive functions
- Relations and their properties
- Representing relations: matrices and digraphs
- Transitive closure and Warshall's algorithm
- 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
- Groups, semigroups and monoids
- Subgroups, abelian and cyclic groups
- Congruence relations and quotient structures
- Rings, integral domains and fields
- Hamming distance and linear block codes
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, Hasse diagrams and lattices
- Boolean algebra and Boolean rings
- SOP and POS forms
- Karnaugh maps
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
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
- Graph terminology and special graphs
- Graph representation and isomorphism
- Euler and Hamilton paths
- Planar graphs and graph colouring
Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).