4CS2A DISCRETE MATHEMATICAL STRUCTURES
Unit I
Sets: Definition and types, Set operations, Partition of set, Cardinality (Inclusion-
Exclusion & Addition Principles), Recursive definition of set.
Functions: Concept, Some Special Functions (Polynomial, Exponential &
Logarithmic, Abslute Value, Floor & Ceiling, Mod & Div Functions), Properties of
Functions, Cardinality of Infinite Set, Countable & Uncountable Sets, The
Pigeonhole & Generalized Pigeonhole Principles, Composition of Functions.
Unit II
Relations: Boolean Matrices, Binary Relation, Adjacency Matrix of Relation,
Properties of Relations, Operations on Relations, The Connectivity Relations,
Transitive Closure-Warshall’s Algorithm, Equivalence relations- Congruence
Relations, Equivalence Class, Number of Partitions of a Finite Set, Partial & Total
Orderings.
Unit III
Proof Methods: Vacuous, Trivial, Direct, Indirect by Contrapositive and
Contradiction, Constructive & Non-constructive proof, Counter example. The
Division Algorithm, Divisibilty Properties (Prime Numbers & Composite Numbers),
Principle of Mathematical Induction, The Second Principle of Mathematical
Induction, Fundamental Theorem of Arithmetic.
Algorithm Correctness: Partial Correctness, Loop Invariant. Testing the partial
correctness of linear & binary search, bubble & selection sorting.
Unit IV
Graph Theory: Graphs – Directed, Undirected, Simple,. Adjacency & Incidence,
Degre of Vertex, Subgraph, Complete graph, Cycle & Wheel Graph, Bipartite &
Complete Bipartite Graph, Weighed Graph, Union of Simple Graphs. Complete
Graphs. Isomorphic Graphs, Path, Cycles & Circuits Euclerian & Hamiltonian
Graphs.
Planar Graph: Kuratowski’s Two Graphs, Euler’s Formula, Kuratowski’s Theorem.
Trees: Spanning trees- Kruskal’s Algo, Finding Spanning Tree using Depth First
Search, Breadth First Search, Complexity of Graph, Minimal Spanning Tree.
Unit V
Language of Logic: Proposition, Compound Proposition, Conjunction, Disjunction,
Implication, Converse, Inverse & Contrpositive, Biconditional Statements,
tautology, Contradiction & Contingency, Logical Equivalences, Quantifiers,
Arguments.
