Subject Name: Discrete Structure and Combinatorics Subject Code: TMC 104
Course Name: Master of Computer Applications (MCA)
1 Contact Hours: 45 L 3 T 0 P 0
2 Examination Duration(Hrs): Theory 0 3 Practical 0 0
3 Relative Weightage: CWE: 25 MTE: 25 ETE: 50
4 Credits: 0 4
5 Semester: *
Autumn Spring Both
6 Pre-Requisite: Basic Set Theory and Elementary Algebra
7 Subject Area: Mathematics
8 Objective: To familiarize students with the concepts of Mathematics needed in
Computer Science.
9 Course Outcome:
CO 1 Be able to construct simple mathematical proofs and possess the ability to verify them
CO 2 Have substantial experience to comprehend formal logical arguments.
CO 3 Be skillful in expressing mathematical properties formally via the formal language of
propositional logic and predicate logic.
CO 4 Be able to specify and manipulate basic mathematical objects such as sets, functions,
and relations and will also be able to verify simple mathematical properties that these
objects possess.
CO 5 Be able to apply basic counting techniques to solve combinatorial problems.
CO 6 Gain experience in using various techniques of mathematical induction (weak, strong
and structural induction) to prove simple mathematical properties of a variety of
discrete structures.
10 Details of the Course:
Unit CONTENT CONTACT
No. HOURS
1 Sets, Relations and Functions: Countable and Uncountable sets, 7
Relations and their types and compositions, Partial order relations and
Hasse’s diagram; Composition of functions, Inverse of functions,
recursively defined functions.
2 Propositional Logic and Mathematical Induction Basic logical 7
operations, Tautologies, Contradictions, Algebra of proposition,
Logical implication, Logical equivalence and Validity; Normal forms,
Rules of Inference, Predicates and Quantifiers; Mathematical
Graphic Era (Deemed to be University), Computer Applications 2020 / Review-01
Effective from Academic Year 2020-21
Induction.
3 Combinatorics and Discrete Numeric Functions Fundamental 10
Principles, Factorial Notations, Permutations and Combinations;
Pigeonhole principle, Binomial Theoram and Multimonial coefficients;
Discrete Numeric Functions, Recurrence relations and Generating
Functions.
4 Group Theory Semi group, monoid, Group, Abelian Group, Subgroup 11
and their properties, Cyclic group, Cosets, Lagrange’s theorem,
Permutation groups, Homomorphism, Isomorphism and
Automorphism of Groups; Ring, Integral Domain and Field.
5 Graph Theory Defination and applications of Graph; types of graph; 10
SubGraph, isomorphic graph, Eulerian and Hamiltonian graph;
Operation and representation of graphs; Planar graph and Coloring of
graphs;
TOTAL 45
11 Suggested Books:
Sl. NAME OF AUTHERS/BOOKS/PUBLISHERS YEAR OF
NO. PUBLICATION
1 S Lipschutz and M. Lipson, Discrete Mathematics, TMH. 2009
2 J. P. Tremblay and R. Manohar, Discrete Mathematical Structure with 1997
Application to Computer Science, TMH.
3 K. H. Rosen, Discrete Mathematics and Its Applications, TMH. 2007
4 D. Alan & L. Kenneth, Applied Discrete Structures for Computer 2000
Science, Galgotia Pub. Pvt. Ltd.
5 J. L. Gersting, Mathematical Structure for Computer Science, W. H. 1993
Freeman& Macmillan.
Graphic Era (Deemed to be University), Computer Applications 2020 / Review-01
Effective from Academic Year 2020-21
