DISCRETE MATHEMATICS

Paper Code: 
BCA 201
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

This module is designed to acquaint students with the basic concepts of matrices and determinants, coordinate geometry, relations and graphs.

 

12.00
Unit I: 

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

 

12.00
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.

 

12.00
Unit III: 

Ordered Relations & Structures: Partially orderd sets, external elements of partially ordered sets, lattices, finite Boolean algebra, functions on Boolean Algebra, Boolean Functions as Boolean Polynomials.

 

12.00
Unit IV: 

Trees:  Introduction, labeled trees, m-ary trees, undirected trees, properties of tree, Spanning tree, Minimal spanning tree (Prim’s algorithm).

 

12.00
Unit V: 

Graphs Theory: Graphs, undirected graphs, weighted graph, paths & cycles, Euler graph & cycles, Hamiltonian graph & cycles, shortest path algorithm  ( Djikstras algorithm).

 

ESSENTIAL READINGS: 
  1. Bernard Kolmann, Robert C. Busby and Sharon Ross, ”Discrete Mathematical Structures”, Third edition, PHI, 1997.

 

REFERENCES: 
  1. Schaum’s Outline series, “Discrete Maths”, Tata McGraw Hill
  2. G.N. Purohit, “Graph Theory”, Jaipur Publishing House
  3. C.L. Liu, “Elements of Discrete Mathematics”, McGraw Hill

 

Academic Year: 
2014-15
  • Printer-friendly version