MCA 104: Discrete Mathematical Structures

Lectures: 4 Periods/Week Sessional Marks: 20
University Exam: 3 Hours University Examination Marks: 80


UNIT-I
The Foundations: Logic and Proofs
Propositional Logic – Propositional Equivalences – Predicates and Quantifiers – Nested Quantifiers – Rules of Inference – Introduction to Proofs – Proof Methods and Strategy .
Basic Structures: Sets, Functions, Sequences and Sums
Sets – Set Operations – Functions – Sequences and Summations.
The Fundamentals : Algorithms ,The Integers and Matrices
Algorithms – The Growth of Functions – Complexity of Algorithms – The Integers And Divisions – Primes and Greatest Common Divisors – Integers and Algorithms – Applications of Number Theory – Matrices .
Introduction and Recursion
Mathematical Induction – Strong Induction and Well-Ordering – Recursive Definitions and Structural Induction – Recursive Algorithms – Program Correctness.

UNIT-II
Counting
The Basics of Counting – The Pigeon Hole Principle – Permutations and Combinations – Binomial Coefficients – Generalized Permutations and Combinations – Generating Permutations and Combinations .
Advanced Counting Techniques
Recurrence Relations – Solving Linear Recurrence Relations – Divide and Conquer Algorithms and Recurrence Relations – Generating Functions – Inclusion – Exclusion – Applications of Inclusion & Exclusion

UNIT-III
Relations
Relations and Their Properties – n-ary Relations and Their Applications – Representing Relations – Closures of Relations – Equivalence Relations – Partial Orderings .
Graphs
Graphs and Graph Models – Graph Terminology and Special Types of Graphs – Representing Graphs and Graph Isomorphism’s – Connectivity – Euler and Hamilton Paths – Shortest Path Problems – Planar Graphs - Graph Coloring

UNIT-IV
Trees
Introduction to Trees – Applications of Trees – Tree Traversal – Spanning Trees – Minimum Spanning Trees
Boolean Algebra
Boolean Functions – Representing Boolean Functions – Logic Gates – Minimization of Circuits .

Text Books

  1. Kenneth H Rosen, “Discrete Mathematics & its Applications”,6th Edition, McGraw-Hill (2007)
    Chapters : 1 to 10
Reference Books
  1. Ralph P. Grimaldi, B.V. Ramana, “Discrete and Combinational Mathematics”, 5th Edition, Pearson Education (2008)..
  2. Swapan Kumar Sarkar, “A Text Book of Discrete Mathematics”, S.Chand (2008).
  3. D.S.Malik and M.K.Sen, “Discrete Mathematical Structures”, Thomson (2006).