**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**

- L. Liu; Elements of Discrete Mathematics

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

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