Course: Mathematics
Prerequisite: The prerequisite for discrete mathematics is to have understanding of
algebra, geometry, and pre-calculus.
Semester: Core: Program/Class:
II DSC M.Sc. (Mathematics)
Course Code: Course Title:
PGMAT114 Discrete Mathematical
Structures
Course Outcomes:
After studying this course, the student will be able to
CO1: Understand the fundamental concepts, principles, and applications of
combinatorics, including permutation and combination, binomial theorem, and
multimodal coefficients.
CO2: Understand discrete numeric functions and generating functions. Define
linear recurrence relations with constant coefficients.
CO3: Understand the fundamental concepts of propositional logic, including
propositions, logical connectives, truth tables, tautologies, and contradictions, and apply
this knowledge to analyze and evaluate logical expressions.
CO4: Identify and analyze equivalence relations and partial ordering relations in various
contexts.
CO5: Develop a comprehensive understanding of graph theory fundamentals and apply
them to analyze and study various types of graphs, including their properties,
connectivity, and planarity.
CO 6: Analyze and describe the properties of trees, identify and construct spanning trees
in graphs, understand the concept of minimal spanning trees and algorithms for their
determination.
or
CO 6: Understand the groups, including their definitions, properties, and various types
such as Abelian groups and permutation groups.
Topics
Unit I: Combinatorics: Introduction, Permutation and combination, Binomial
Theorem, Multimodal Coefficients.
Unit II: Recurrence Relation and Generating Function: Introduction to Recurrence
Relation and Recursive algorithms, linear recurrence relations with constant coefficients,
Homogeneous solutions, Particular solutions, Total solutions.
Unit III: Generating functions, Solution by method of generating functions. The
Pigeonhole and Generalized Pigeonhole Principles.
Unit IV: Propositional Logic: Proposition, First order logic, Basic logical operation,
truth tables, tautologies, Contradictions.
Unit V: Algebra of Proposition, logical implications, logical equivalence, predicates,
Normal Forms, Universal and existential quantifiers. 2-way predicate logic.
Unit VI: Posets Hasse Diagram and Lattices: Equivalence relation, Partial ordering
relation, Job-Scheduling problem. Introduction of partially ordered set.
Unit VII: Hasse diagram of partially ordered set, isomorphic ordered set, well ordered
set, properties of Lattices, bounded and complemented lattices.
Unit VIII: Graph Theory: Introduction and basic terminology of graphs, Planar
graphs, Multigraphs and weighted graphs, Isomorphic graphs, shortest path in weighted
graph.
Unit IX: Paths, Cycles, connectivity, Hamiltonian paths and circuits
Unit X: Graph coloring, chromatic number, Isomorphism and Homomorphism of
graphs, matching, vertex/edge covering.
Unit XI: Trees- Properties, Binary and Rooted Tree, Planar graph, region,
homeomorphic graph and Dual graphs
Unit XII: Spanning Tree, Minimal Spanning Tree, Matrix representation of graphs.
Suggested Books:
1. Edgar G. Goodaire and Michael M. Parmenter, (2005), Discrete Mathematics with
Graph Theory, Third Edition, Pearson Education (Singapore) P. Ltd., Indian Reprint.
2. Rosen, Kenneth H., (2012), Discrete mathematics and its applications, Seventh
Edition, McGraw Hill Education.
3. Mott J.L., Kendel A. and Baker T.P., (2008), Discrete mathematics for
Computer Scientists and Mathematicians, Prentice Hall of India Pvt Ltd.
4. Liu C.L. and Mohapatra D.P., (2008), Elements of discrete mathematics, Tata
McGraw Hill.
