SYLLABUS

UNIT-1 Sets, Cardinality, Principal of inclusion and exclusion, Mathematical induction,
Relations and Functions, Binary relations, Equivalence relations and partitions, Partial
orderrelations and Lattices, Chains and Anti-chains. Pigeonhole principle.

UNIT-2 Boolean Algebra- Lattices and Algebraic structure, Duality, Distributive and
Complemented Lattices, BooleanLattices, Boolean functions and Boolean expression.
Fundamental theorem of arithmetic, Divisibility in Z, Congruence's, Chinese reminder
theorem, Euler's functions, Primitive roots.

UNIT-3 Logic and propositional calculus, Simple and compound propositions, Basic
logical operations, Truth tables, Tautologies and contradictions, Propositional functions,
Quantifiers. Discrète numeric functions, Generating functions, Recurrence relations and
Recurrence algorithms, Linear recurrence relation with constant coefficients and their
solutions, Total solutions, Solution by the methodoïgenerating functions.

UNIT-4 Basic concepts of graph theory, Types of graph (Connected Graphs, Regular
graphs, Planar graphs), walk, Paths& Circuits, Shortest path problem. Operations on
graphs (union,join, products)

UNIT-5 Matrixrepresentationof graphs, Adjacency matrices, Incidences matrices,
Tree, Spanning tree, Minimummspanning tree, Distance between vertices, Center oftree,
Binary tree, Rootedtree. Hamiltonian and Eulerian graphs