SGBAU · Second Year B.E. Information Technology · NEP 2020
Discrete Structure & Graph Theory
3IT200PC · Semester III · 3 credits · IE 40 + ESE 60
Unit 1: Mathematical Logic
7 hoursStatements, 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
Unit 2: Set Theory
7 hoursBasic 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
Unit 3: Algebraic Structures
7 hoursAlgebraic 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
- Binary operations and algebraic systems
- Groups, monoids and semigroups
- Group codes and homomorphism
- Context-free grammars and derivations
Unit 4: Lattice & Boolean Algebra
7 hoursLattices as partially ordered sets; Boolean algebra and Boolean functions, their representation and minimisation.
Examined in the 60-mark end-semester paper
- Partial orders, Hasse diagrams and lattices
- Boolean algebra and Boolean rings
- SOP and POS forms
- K-map minimisation
Unit 5: Graph Theory
7 hoursBasic 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
Unit 6: Trees
7 hoursTrees 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).