Discrete Mathematics

Paper Code: 
Contact Hours: 
Max. Marks: 
Unit I: 

Counting and Recursion: Permutations and Combinations, Principle of Inclusion & Exclusion, Pigeonhole Principle, Mathematical induction, Recurrence relation, Generating Functions.

Unit II: 

Relation & Diagraphs : Product sets & Partitions, Relations & diagraphs, paths in relation & diagraphs, properties of relations, Equivalence relations, computer representation of relations & diagraphs, manipulation of relations.


Unit III: 

Ordered Relations & Structures: Partially ordered sets, extermal elements of partially ordered sets, Bounding Elements, Well Ordered Set, Lattices, Principle of Duality, Bounded, Distributed, and Complemented Lattices, Finite Boolean algebra, functions on Boolean algebra.

Unit IV: 

Trees:  Introduction, labeled trees, m-ary trees, undirected trees, properties of tree, Spanning tree, Minimal spanning tree, Binary search trees.

Unit V: 

Graphs Theory: Basic Terminology, types of graph, paths & cycles, Euler graph & cycles, Hamiltonian graph & cycles, shortest path algorithm ( Djikstras algorithm), Graph Isomorphism, Planar Graph, Graph colorings and chromatic number.

Essential Readings: 
  1. Bernard Kolmann, Robert C. Busby and Sharon Ross, ”Discrete Mathematical Structures”, Third edition, PHI, 1997.
  2. C.L. Liu, “Elements of Discrete Mathematics”, McGraw Hill
  3. V. K. Balakrishnan, Introductory discrete mathematics, Prentice Hall, 1996.
  4. Richard Johnsonbaugh, Discrete Mathematics, 7th Edition, Pearson Education, 2008.
  1. Norman Biggs, Discrete mathematics, Oxford University Press, 2003.
  2. Kenneth H.Rosen, “Discrete Mathematics and its Applications, Fifth Edition, Tata McGraw Hill Pub. Co. Ltd., New Delhi, 2003.
  3. Richard Johnsonbaugh, “Discrete Mathematics", Fifth Edition, Pearson Education Asia, New Delhi, 2002.
  4. Trembly J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science, Tata McGraw Hill Pub. Co. Ltd, New Delhi, 2003.
  5. Ralph. P. Grimaldi, “Discrete and Combinatorial Mathematics: An Applied Introduction, Fourth Edition,  Pearson Education Asia, Delhi, 2002.