SYLLABUS
DISCRETE STRUCTURE & GRAPH THEORY
Unit I: The Foundations: Logic and Proofs: Propositions,
Truth Tables, Compound Propositions, Logical Operators,
Logic and Bit Operations; Logical Equivalences, De
Morgan’s Laws, Satisfiability: Applications and Solving
Problems; Predicates, Quantifiers: Restricted Domains,
Precedence, Logical Equivalences; Rules of Inference for
Propositional Logic, Use to Build Arguments.
Unit II: Sets, Functions and Relation: Introduction, Venn
Diagrams, Subsets, Size of a Set, Power Sets, Cartesian
Products, Set Notation with Quantifiers, Truth Sets and
Quantifiers, Set Operations ,Functions, Inverse Functions,
Compositions and Graphs of Functions, Partial Functions;
Sequences, Summations; Countable Sets, An Uncountable
Set; Functions as Relations, Relations on a Set, Properties
m
of Relations, Combining Relations; Representing Relations
co
Using Matrices; Representing Relations, Closures of
Relations, Equivalence Relations.
n.
Unit III: Algebraic Structures: Algebraic Systems:
Examples and General Properties; Semigroups and
io
Monoids: Homomorphism of Semigroups and Monoids,
at
Subsemigroups and Submonoids; Groups: Definitions,
Subgroups and Homomorphisms, Cosets and Lagrange’s
lic
Theorem, Normal Subgroups, algebraic Systems with Two
Binary Operations; Group Codes: The Communication
ub
Model and Basic Notions of Error Correction, Hamming
Distance.
ap
Unit IV: Boolean Algebra: Lattices, Boolean Algebra:
Boolean Functions, Representing Boolean Functions, sum
ty
of product expansions, Functional Completeness, Logic
di
Gates, Combinations of Gate, Minimization of Circuits,
Karnaugh Maps.
.a
w
Unit V: Tree: Introduction, Rooted Tree, ordered rooted
w
tree, tree as model, Properties of Trees, Applications of tree,
Binary Search Trees, Decision Trees, Prefix Codes,
w
Huffman Coding, Game Trees, Tree traversal, Preorder
Traversing, Inorder Traversing, Post order Traversing,
Spanning Tree, Minimum spanning tree.
Unit VI: Graph: Graph Models; Basic Terminology, Special
Simple Graphs, Bipartite Graphs, Matchings, Applications
of Special Types of Graphs, New Graphs from Old; Graph
Representation, Adjacency and Incidence Matrices,
Isomorphism of Graphs, Determining Isomorphism; Paths,
Connectedness in Undirected Graphs and Directed Graphs,
Paths and Isomorphism, Counting Paths Between Vertices;
Euler Paths and Circuits, Hamilton Paths and Circuits,
Applications of Hamilton Circuits; Planar Graphs: Euler’s
Formula, Kuratowski’s Theorem; Graph Coloring:
Introduction, Applications of Graph Colorings;
