20CE 303: DISCRETE MATHEMATICS
Teaching Scheme Examination Scheme
Lectures: 3 Hours / Week In Semester: 50 Marks
Tutorials : 1 Hour / Week End Semester: 50 Marks
Credits: 4
Course Objectives:
To facilitate the learner to
1. To understand Discrete Mathematics concepts and their significance in Computer
Engineering.
2. To understand set theory, logic and apply reasoning to solve problems.
3. To solve problems based on algebraic systems, permutation and combination.
4. To solve problems on functions and relations and learn the basic properties of graphs
and trees.
Course Outcomes:
After completion of the course, students will be able to
1. Solve problems on set using Venn diagram, theorems like the principle of inclusion-
exclusion and mathematical induction and solve problems on relations and functions.
2. Apply concepts of propositional calculus for solving problems, formal proofs,
reasoning and represent problems using first-order logic.
3. Apply the concepts of groups, permutations and combinations to solve problems.
4. Apply basic terminologies of graphs and trees to solve problems on paper.
Unit I: Sets and Mathematical Induction (07)
Significance of Discrete Mathematics in Computer Engineering, Sets, Subset, Universal Set,
Empty Set, Algebra of Sets and Duality, Operations on Sets, Finite and Infinite Sets, Un
Countably Infinite Sets, Multi-Sets, Power Set, Venn Diagram, Principle of Inclusion and
Exclusion, Principle of Mathematical Induction, Applications of Set.
Unit II: Logic and Propositional Calculus (06)
Propositions, Logical connectives, Conditionals and Bi-Conditionals, Tautology,
Contradiction, Contingency, Logical Equivalences, Algebra of Propositions, Logical
Implications, Conjunctive and disjunctive Normal Forms, Rules of Inference, Predicates and
Quantifiers, Nested Quantifiers, Applications of Logic.
Unit III: Groups, Rings and Permutations and Combinations (08)
Algebraic Systems, Groups, Semi Groups, Monoids, Subgroups, Introduction to Isomorphism,
Homomorphism and Automorphism of groups, Cosets and Normal Subgroups, Introduction to
Rings, Integral Domain and Field, Applications of Algebraic System, Introduction to
Permutations and Combinations.
Unit IV: Relations and Functions (08)
Introduction to Relations, Product Sets, Pictorial Representation of Relations, Composition of
Relations, Closure of Relations, Warshall’s Algorithm, Properties of Binary Relations,
Equivalence Relations and Partitions, Partial Ordering Relations, Hasse Diagram, Lattices,
Chains and Anti-Chains.
Functions: Composition of Functions, Injective function, Surjective function, Bijective
function, Invertible Functions, Hash function: Division method, Midsquare method and Folding
method, Pigeonhole Principle.
Unit V: Graph Theory (07)
Basic Terminology, Multi-Graphs and Weighted Graphs, Sub-Graphs, Isomorphic Graphs,
Complete, Regular and Bipartite Graphs, Operations on Graph, Factors of a Graph, Paths and
Circuits, Connectivity, Hamiltonian and Euler Paths and Circuits, Planar Graph and Theorem,
Shortest Path in Weighted Graphs (Dijkstra’s Algorithm), Applications of Graph-Graph
Coloring Problem, Travelling Salesman Problem.
Unit VI: Trees (06)
Basic Terminologies in Trees and Properties of Trees, Binary Search Trees, Tree Traversal,
Spanning Trees, Fundamental Circuits and Cut Sets, Minimal Spanning Trees, Kruskal’s and
Prim’s Algorithms for Minimal Spanning Trees, Transport Network.
Text Books:
1. C. L. Liu and D. P. Mohapatra, “Elements of Discrete Mathematics”, 4th Edition, Tata
McGraw-Hill, 2017, ISBN 978-1-25-900639-5.
2. Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 7th Edition, 2012,
Tata McGraw-Hill, ISBN 978-0-07-338309-5.
Reference Books:
1. B. Kolman, R. Busby and S. Ross, “Discrete Mathematical Structures”, 6th Edition,
Pearson Education, 2009, ISBN 81-7808-556-9.
2. Seymour Lipsehutz and Marc Lars Lipson “Discrete Mathematics”, 3rd Special Indian
Edition, ISBN-13: 978-0-07-060174-1.
3. J. P. Tremblay and R. Manohar, “Discrete Mathematical Structures with Applications
to Computer Science”, 1997, Tata McGraw-Hill, ISBN 0-07- 463113-6.
4. E. Goodaire and M. Parmenter, “Discrete Mathematics with Graph Theory”, third
edition, Pearson Education, 2008, ISBN 81 – 7808 – 827 – 4.
5. N. Deo, “Graph Theory with application to Engineering and Computer Science”,
Eastern Economy Edition, Prentice Hall of India, 1990, 0 – 87692 – 145 – 4.
Online/Web/Other References:
1. 12 Week NPTEL course, [Link]
List of the Tutorial Assignments
Every student should perform 12-14 tutorials which will cover topics of all units mentioned
in the Syllabus of Discrete Mathematics.
Following list of tutorials can be considered as a guideline for designing tutorials in such a
way that all topics should be distributed and covered amongst all batches.
1. Problems on set, multi-set operations, Venn diagram and algebra of sets.
2. Problems on Principle of Inclusion-Exclusion.
3. Illustrative example solving using Mathematical Induction.
4. Translating English statement into propositional logic and predicate logic.
5. Problems on groups.
6. Problems on permutation and combination.
7. Representation of relations and functions, closure of relations and equivalence relation.
8. Problems on partitions, POSET’s, Hasse diagram and Lattices.
9. Problems on Warshall's Algorithm.
10. Problems on composition of functions, invertible functions, recurrence relation.
11. Problems on multi-graphs and weighted graphs, sub-graphs, isomorphic graphs.
12. Solve problems for shortest path in weighted graphs (Dijkstra’s algorithm)
13. Solve problems on Kruskal’s and Prim’s algorithms for minimal spanning trees.
14. Solve problems on Cut sets and Transport network