MCA – 1 SEMESTER

 

MCA-105 DISCRETE MATHEMATICS

 

 

L T P Total Credits-4
4 0 0 4 Duration of Exam- Three hours

 

 

Sets and Propositions

 

Introduction, Combination of sets, Finite and Infinite sets, Uncountably Infinite Sets, Mathematical Induction, Principle of Inclusion and Exclusion, Multisets, Properties of Binary Relations, Equivalence Relations and Partitions, Partial Ordering Relations, Functions and Pigeonhole Principle, Propositions.

 

Algebraic System

 

Definitions and elementary properties of algebraic structures, Semigroups, monoids and submonoids, Groups and subgroups, Homomorphisms and Isomorphisms of Monoids and Groups, Definition and Examples of Rings and Subrings, Types of Rings, Commutative Ring, Ring with Unity, Ring with or without Zero divisions, Integral Domain, Division Ring, Relation of Isomorphism in the set of rings, Field, its characteristics and subfield.

 

Graphs and Planar Graphs

 

Introduction, Basic Terminology, Multigraphs and Weighted Graphs, Paths and Circuits, Shortest Paths in Weighted Graphs, Eulerian Paths and Circuits, Hamiltonian Paths and Circuits, Planar Graphs, Trees, Rooted Trees, Path Lengths in Rooted Trees, Binary Search Trees, Spanning Trees and Cut-sets, Minimum Spanning Trees.

 

Permutations, Combinations and Recurrence Relations

 

The Rules of Sum and Product, Permutations, Combinations, Generation of Permutations and Combinations, Recurrence Relations, Linear Recurrence Relations with Constant Coefficients, Homogeneous Solutions, Particular Solutions, Total Solutions, Solution by the Method of Generating Functions.

 

Suggested References

 

  1. L. Liu; Elements of Discrete Mathematics

 

  1. Kenneth Kalmanson: An Introduction to Discrete Mathematics and its Applications, Addison Wesley Publishing Co., 1986.

 

  1. P. Tremblay: Discrete Mathematical Structures with Applications to Computer Science, McGraw Hill, N.Y., 1977.

 

Leave a Reply

Leave a Reply

Your email address will not be published.