Teaching Scheme
Course Credits Assigned
Course Name (Contact Hours)
Code
Theory Pract. Tut. Theory Pract. Tut. Total
Discrete
Structures
2013112 3 - - 3 - - 3
and Graph
Theory
Theory Term Pract. Total
Course Internal Assessment End Exam work / Oral
Course Name
Code Test Test Total Sem Duration
1 2 Exam (in Hrs)
Discrete Structures
2013112 20 20 40 60 2 -- -- 100
and Graph Theory
Rationale:
Mathematics forms the foundation of computer science and engineering. The study of Discrete Structures
and Graph Theory enables students to develop strong logical reasoning, combinatorial techniques, and
mathematical structures that are essential in programming, algorithm design, networking, database design,
artificial intelligence, and cryptography.
Course Objectives:
1) Cultivate clear thinking and creative problem solving.
2) Thoroughly train in the construction and understanding of mathematical proofs. Exercise common
mathematical arguments and proof strategies.
3) To apply graph theory in solving practical problems.
4) Thoroughly prepare for the mathematical aspects of other Artificial Intelligence and Data Science
Engineering courses.
5) Solve real-world problems using counting principles, recurrence relations.
6) Strengthen mathematical foundations for research and higher studies in Artificial Intelligence and
Data Science Engineering.
Course Outcomes:
1) Understand the notion of mathematical thinking, mathematical proofs and to apply them in
problem solving using set theory and logic.
2) Apply properties of Relation sets in real-life problem-solving domains.
3) Apply properties of Function sets in real-life problem-solving domains
4) Apply counting principles, including the Pigeonhole Principle and Inclusion-Exclusion Principle,
to solve combinatorial problems.
5) Apply algebraic structure for a given mathematical problem.
6) Apply graph theory in solving computing problems.
DETAILED SYLLABUS:
Sr. CO
Name of Module Detailed Content Hours
No. Mapping
Basic Set Theory, Logical Operators, Truth Tables,
Cartesian product, Types of Functions. Basic
0 Prerequisite Algebra and Number Theory, Fundamental 1
Counting Principle, Permutations, Combinations.
Graph Basics.
Set Theory: Sets, Subsets, Universal and Empty
Sets, Set Operations, Set Representation, Laws of
Set theory.
Logic: Propositional Logic, Predicate Logic,
Quantifiers (Universal and Existential).
Types of Mathematical Proof: Direct proof,
Crisp Set Theory Proof by contradiction, Proof by deduction, Proof
I 7 CO1
and Logic by cases, Proof by exhaustion, Proof by
counterexample, Mathematical induction.
Self-learning Topics: PROLOG / LISP
programming to create expert system using
Propositional and Predicate Logic, Other types of
logic and sets.
Relations: Definition, Representation of
Relations, Properties of Relations, Equivalence
Relations, Equivalence Classes, Closures of
Relations, Warshall’s algorithm.
Posets and Lattice: Partial Order Relations, Poset,
Mathematical Hasse Diagram, Chain and Anti chains, Lattice,
II 8 C02
Relations Types of Lattices, Sub lattice.
Self-learning Topics: Practical applications of
relations in real life in the field of Database
Management, Economics, Social Network, Sports,
Medical Diagnosis, Weather, etc.
Functions: Types: Injective, Surjective, and
Bijective Functions. Composition, Inverse
Functions. Real life applications of Functions.
III Functions Self-learning Topics: Practical applications of 3 CO3
function in Neural Network, Determining risk
factors for insurance rates, Taxes and tax brackets,
Vending machines, etc.
Pigeonhole Principle, Inclusion-Exclusion
Principle.
Recurrence relations, Solving recurrence relations
IV Counting Self-learning Topics: Applications of Recurrence 5 CO4
Relations – Analysis of recursive algorithms in
computing. Combinatorial Problem Solving –
Using counting techniques in probability and
decision-making.
Algebraic structures with one binary operation:
Semi group, Monoid, Groups, Subgroups, Abelian
Group, and Cyclic group.
Algebraic
V Algebraic structures with two binary operations: 7 CO5
Structures
Ring.
Self-learning Topics: Error Correcting codes.
Types of graphs, Graph Representation, Sub
graphs, Operations on Graphs, Walk, Path, Circuit,
Connected Graphs, Disconnected Graph,
Components, Homomorphism and Isomorphism of
Graphs, Euler and Hamiltonian Graphs, Planar
Graph, Cut Set, Cut Vertex, Real life applications
of Graph Theory.
VI Graph Theory 8 CO6
Self-learning Topics: Network Flow Problems –
Understanding flow in networks and its
optimization. Graph Coloring Applications in
Scheduling – Use of graph coloring in timetabling
and resource allocation. Optimization Techniques
– Application of graphs in shortest path problems,
spanning trees, and clustering.
Text Books:
1. Susanna S. Epp, “Discrete Mathematics with Applications”, 5th Edition, Cengage Publications.
2. Ralph P. Grimaldi, “Discrete and Combinatorial Mathematics”, 5th Edition, Pearson Publications.
3. Edgar Goodaire and Michael Parmenter, “Discrete Mathematics and Graph Theory”, 3rd Edition,
Pearson Publications.
Reference Books:
1. Kenneth A. Ross, “Discrete Mathematics”, 5th Edition, Pearson Publications.
2. Swapan Kumar Sarkar, “Textbook of Discrete Mathematics”, 9th Edition, S. Chand Publications.
3. Bernad Kolman, Robert Busby, Sharon Cutler Ross, Nadeem-ur-Rehman, “Discrete Mathematical
Structures”, 6th Edition, Pearson Education.
4. T. Veera Rajan, “Discrete mathematics with Graph Theory and Combinatorics”, McGraw Hill
Publications.
5. C. L. Liu “Elements of Discrete Mathematics”, second edition 1985, McGraw-Hill Book Company.
Reprinted 2000
Online References:
Sr. No. Website Name
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
Assessment:
o Internal Assessment Test (IAT) for 40 Marks:
● IA will consist of Two Compulsory Internal Assessment Tests. Approximately 40% to 50%
of the syllabus content must be covered in the IAT-I and the remaining 40% to 50% of the
syllabus content must be covered in the IAT-II.
o End Semester Theory Examination for 60 Marks:
Question paper format :
● Question Paper will comprise a total of six questions each carrying 15 marks Q.1 will be
compulsory and should cover the maximum contents of the syllabus.
● Remaining questions will be mixed in nature (part (a) and part (b) of each question must
be from different modules. For example, if Q.2 has part (a) from Module 3 then part (b)
must be from any other Module randomly selected from all the modules).
● A total of four questions need to be answered.