COURSEPACK

SCHE
ME
The scheme is an overview of work-integrated learning opportunities and gets
students out into the real world. This will give what a course entails.

Course Title Discrete Mathematics Course Type Theory

Course Code C1UC224T Class
Activity Credits Credit Hours Total Number of Assessment in
3 3 Classes per Semester Weightage
Lecture
Instruction Tutorial 0 0

Practical
Tutorial
Theory
delivery

study
Self-

SEE
Practical 0 0

CIE
Self-study 0 0

Total 3 3
45 0 0 0 50% 50%
Course Lead Course Dr. Aliya Naaz Siddqui
Coordinator Ms. Neelam Kumari
Names Theory Practical
Course
Instructors

COURSE OVERVIEW
The students who are successful in discrete mathematics will be able to generalize from a single
instance of a problem to an entire class of problems. As it covers probabilities, trees, graphs, logic,
mathematical thinking, and much more. This course is important in the sciences, for example
understanding of DNA sequences in molecular biology, and useful in studying and describing
objects and problems in all branches of computer science, such as computer algorithms,
programming languages, cryptography (using in Data Security Council of India and IBM Security
Guardium), and software development.

PREREQUISITE COURSE
PREREQUISITE COURSE NO
REQUIRED
If, yes please fill in the Details Prerequisite Prerequisite course name
course code
NIL NIL

COURSEPACK | FORMAT
 COURSE OBJECTIVE
The objective of this course is to familiarize the prospective computer scientists with the techniques of
mathematical reasoning, logical thinking, abstract mathematical discrete structures so that they may
apply
a particular set of mathematical facts in relevant situations.

COURSE OUTCOMES (COs)

After the completion of the course, the student will be able to:

CO No. Course Outcomes

CO1 Remember the concepts in logical reasoning, set & graph theory. (WK2)
CO2 Examine different algebraic and graphical structures. (WK2)
CO3 Apply logical reasoning, proof methods, and counting principles in problem-solving.
(WK2)
CO4 Demonstrate proficiency in proofs, set operations, functions, and graph analysis.
(WK2)

BLOOM’S LEVEL OF THE COURSE OUTCOMES

Bloom's taxonomy is a set of hierarchical models used for the classification of educational learning
objectives into levels of complexity and specificity. The learning domains are cognitive, affective,
and psychomotor.

THEORY

Rememb Understa Apply Analyse Evaluat Create

CO No. er nd BTL2 BTL3 BTL4 e BTL2 BTL6
BTL1
1 🗸
2 🗸
3 🗸
4 🗸

COURSEPACK | FORMAT
PROGRAM OUTCOMES (POs): AS DEFINED BY CONCERNED THE APEX BODIES

PO1: Engineering Knowledge: Apply knowledge of mathematics,

natural science, computing, engineering fundamentals and an
engineering specialization as specified in WK1 to WK4 respectively
to develop to the solution of complex engineering problems.

PO2: Problem Analysis: Identify, formulate, review research literature

and analyze complex engineering problems reaching substantiated
conclusions with consideration for sustainable development. (WK1
to WK4)

PO3: Design/Development of Solutions: Design creative solutions for

complex engineering problems and design/develop
systems/components/processes to meet identified needs with
consideration for the public health and safety, whole-life cost, net
zero carbon, culture, society and environment as required. (WK5)

PO4: Conduct Investigations of Complex Problems: Conduct

investigations of complex engineering problems using research-
based knowledge including design of experiments, modelling,
analysis & interpretation of data to provide valid conclusions.
(WK8).

PO5: Engineering Tool Usage: Create, select and apply appropriate

techniques, resources and modern engineering & IT tools, including
prediction and modelling recognizing their limitations to solve
complex engineering problems. (WK2 and WK6)

PO6: The Engineer and The World: Analyze and evaluate societal and
environmental aspects while solving complex engineering problems
for its impact on sustainability with reference to economy, health,
safety, legal framework, culture and environment. (WK1, WK5, and
WK7).

PO7: Ethics: Apply ethical principles and commit to professional ethics,

human values, diversity and inclusion; adhere to national &
international laws. (WK9)

PO8: Individual and Collaborative Team work: Function effectively as

an individual, and as a member or leader in diverse/multi-
disciplinary teams.

PO9: Communication: Communicate effectively and inclusively within

the engineering community and society at large, such as being able
to comprehend and write effective reports and design
COURSEPACK | FORMAT
 documentation, make effective presentations considering cultural,
language, and learning differences

PO10: Project Management and Finance: Apply knowledge and

understanding of engineering management principles and
economic decision-making and apply these to one’s own work, as a
member and leader in a team, and to manage projects and in
multidisciplinary environments.

PO11: Life-Long Learning: Recognize the need for, and have the
preparation and ability for i) independent and life-long learning ii)
adaptability to new and emerging technologies and iii) critical
thinking in the broadest context of technological change. (WK8)

PSO1: Ability to work with emerging technologies in computing requisite to Industry 4.0
PSO2: Demonstrate Engineering Practice learned through industry internship to solve live
problems in various domains.

COURSE ARTICULATION MATRIX

The Course articulation matrix indicates the correlation between Course
Outcomes and Program Outcomes and their expected strength of mapping in
three levels (low, medium, and high).

PSO1

PSO2
PO10

PO11
PO1

PO2

PO3

PO4

PO5

PO6

PO7

PO8

PO9

COs#/
POs

CO1 1 1 1

CO2 2 2 2

CO3 3 3 3

CO4 3 3 3

Note: 1-Low, 2-Medium, 3-High

COURSE ASSESSMENT
The course assessment patterns are the assessment tools used both in formative and
summative examinations.

CIE Weightage End Term

Type of Course IA-2 Exam (ETE)
IA-1 Mid Term Weightage
Exam
Integrated (B) 25 25 50 100
Final 25 25 50
Weightage

COURSEPACK | FORMAT
 Total 100

* Assignment, Quiz, Class test, SWAYAM/NPTEL/MOOCs and etc.

COURSE CONTENT

Content
Syntax, Semantics, Validity and Satisfiability, Basic connectives and Truth
Tables, Logical Equivalence, the laws of logic, Logical implication, Rules of
inference, Normal form (CNF, DNF), Predicate logic, Universal and Existential
quantifiers.
Proof Techniques: Some terminologies, Proof methods and strategies, Forward
proof, Proof by contradiction, Proof by contraposition, Proof of necessity and
sufficiency.

Counting Techniques: Basic counting techniques, inclusion, and exclusion,

pigeon-hole principle, permutation, and combination

Operations and laws of sets, Cartesian product, binary relation, partial order
relation, Equivalence relation, Functions, Bijective function, inverse and
composition of function, size of a set, countable and uncountable set, Cantor’s
diagonal argument and the power set theorem, Schroeder-Bernstein theorem.
Principles of Mathematical Induction: The well -Ordering principle, Recursive
definition, prime numbers, greatest common divisor, Euclidean algorithm, the
fundamental theorem of arithmetic.

Algebraic structures with one binary operation: Semi Group, Monoid, Groups,
Subgroups, Congruence relation and quotient structures, Free and Cyclic
Monoid and Groups, Cosets, Lagrange's theorem, Normal Subgroups,
Permutation and Symmetric groups, Group Homomorphism, Algebraic
structures with two binary operations: Ring, Integral domain, and Field.

Graphs and their properties, degree, connectivity, path cycle, sub graphs,
COURSEPACK | FORMAT
isomorphism, Eulerian and Hamiltonian walks, Graph coloring, and planer
graphs, Trees: Definitions, properties, and examples.

Partial order sets, Hasse diagram, Lattices, and its properties of lattices

COURSEPACK | FORMAT
LESSON PLAN FOR THEORY COURSES (15 weeks * 3 Hours = 45
Classes)
Lec. Topic L/T/P Skills Competency
1. Propositions, logical operators, Truthtables (TT) L
1

Conditional statements, converse, contrapositive,

2. inverse, biconditionals L
2
TT of compound propositions, precedence of logical
L
operators 1.To frame the Logical thinking
3.
logical
3 statements
Tautology, contradiction, logical equivalence, laws, 2. To frame the
L
4. Satisfiability arguments with
4 the help of
mathematical
5. Predicates, quantifiers and logical
L expressions.
5 3. To check the
validity of
6. Rules of Inference
L arguments
6 4. Determine the
logical
7. Normal form- CNF, DNF L equivalency of
7 the compound
statements.
Proof Techniques: Some terminologies, Forward
L
8. proof, Proof by contradiction, Proof by
8 contraposition, Proof of necessity and sufficiency.

9. Basic counting techniques, Inclusion and exclusion L

9 rule

10. Pigeon-hole principle, Generalized pigeon-hole L

10 principle

11. Permutation L
11

12. Combination L
12

13. Set, Venn diagram, Subsets, size of the set, power L

1.To understand
Demonstrate the
13 set, Cartesian Product sets and perform
understanding of
operations and
sets, relations
14. Set operations, set identities, Generalized Unions and L algebra on sets
and functions
Intersections, Computer Representation of Sets determine the
and use them for
COURSEPACK | FORMAT
14 properties of
counting
relation and
techniques
15. Relations, properties of relations, Combining functions,
L identify
15 Relations
equivalence and
partial ordered
16. Equivalence Relation and Classes, partition L relation.
18 Determining the
domain and
17. Functions, one-one, onto, bijection L range
19

18. Inverse and composition functions, floor & ceiling L

20 function

Cardinality of the Set, Countable and Uncountable

19. set, Cantor’s diagonal theorem the power set L
21 theorem, Schroeder-Bernstein theorem

20. Mathematical Induction, Strong induction, the well L

22 ordering Principle

21. Recursive Relation L

23

22. Prime Number and Greatest common divisor of two L

24 numbers

23. Euclidean algorithm L

25

24. The fundamental theorem of arithmetic L

26

25. Introduction of Algebraic Structures: Monoids and L

27 semigroups. Analyze the Study of
basic structures symmetry
26. Introduction of Algebraic Structures: Groups of algebraic
L structures
28

Groups, Subgroups,
27. L
29
Congruence relation
28. L
30
29. Coset, Lagrange's theorem. L
31

COURSEPACK | FORMAT
30. Coset, Lagrange's theorem. L
32

Normal Subgroups, Permutation & Symmetric

31. groups, Group Homomorphism L
33

Normal Subgroups, Permutation & Symmetric

L
32. groups, Group Homomorphism
34
Algebraic structures with two binary operations:
L
Ring, Integral domain, Field.

33.
35
Algebraic structures with two binary operations:
34. Integral domain, Field. L
36
Graph & graph models
35. L
37
Graph Terminology and Special Types of Graphs
36. L
38
Representing Graphs and Graph Isomorphism
37. L
39
38. Connectivity, Euler and Hamilton Paths L
40
1.Basic
39. Planar Graphs, Graph Coloring L terminology of
Able to explain
41 graph, tree, and
basic
path
terminology of a
40. Introduction to Trees& applications L
2.Analyze the
graph Identify
42 relationships
Euler and
between
Hamiltonian
41. Tree Traversal, Spanning Trees, Minimum Spanning different objects
L cycle Represent
or entities
43 Trees 3.To represent
graphs using
adjacency
the interactions
42. Partial ordered set matrices
L between
44 different objects

43. Combination of partial order sets, Hasse diagram L

45

44. Lattices: Definition, Properties of lattices – L

46 Bounded, Complemented

COURSEPACK | FORMAT
 45. Modular and Complete lattice L
7

BIBLIOGRAPHY

 Text Book
T1: Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th Edition,
McGraw Hill Education, 2021.
 Reference Books
R1: J P Trembley, R Manohar, Discrete Mathematical Structures with Applications to
Computer Science, 1st Edition, McGraw-Hill Education, 2017.
R2: Semyour Lipschutz, Marc Lipson, Varsha H. Patil, Discrete Mathematics (Schaum's
Outlines, 3rd Edition, McGraw Hill Education, 2017.

Journals/Magazines/Govt. Reports/Gazatte/Industry Trends

i. https://www.sciencedirect.com/journal/discrete-mathematics
ii. https://www.degruyter.com/journal/key/dma/html?lang=en

Webliography : www.mhhe.com/rosen
https://nptel.ac.in/courses/106106183
 SWAYAM/NPTEL/MOOCs Certification:
https://nptel.ac.in/courses/106106183

PROBLEM-BASED LEARNING
Exercises in Problem-based Learning (Assignments)
S.No Questions Blooo’s
level
K1
1. W Which of these sentences are propositions? What are the truth values of those that are
propositions? a) 2 + 3 = 5. b ) Answer this question.

2. Check whether these statements are wff or not:(a) (p˅q) ∧∼r (b) p˅q∧r K2

Determine whether these biconditionals are true or false. K2

3. a) 2 + 2 = 4 if and only if 1 + 1 = 2. b) 1 + 1 = 2 if and only if 2 + 3 = 4.

Let P(x) be the statement “x = x2.” If the domain consists of the integers, what are these K2
4.
b) ∃xP(x)
truth values?
a) P(1) (11/53/KR)

Determine the truth value of each of these statements if the domain consists of all K2
5. integers.
COURSEPACK | FORMAT
 a) ∀n(n + 1 > n) b) ∃n(2n = 3n)

Use De Morgan’s laws to find the negation of each of the following K2

6.
statements. a) Jasbir is rich and happy b) Rain will bicycle or run

Show that (p → q) ∧ (q → r) → (p → r) is a tautology

tomorrow.
K2
7.
K2
8. Give a direct proof of the theorem “If n is an odd integer, then n2 is odd.”

K2
9. Give a proof by contradiction of the theorem “If 3n+2 is odd, then n is
odd”.

For each of these relations on the set {1,2,3,4}, decide whether it is reflexive, K2
10.
whether it is symmetric, whether it is anti-symmetric, and whether it is transitive.

(a) {(2,2), (2,3), (2,4),(3,2), (3,3), (3,4)}

(b) {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}

(c) {(2,4),(4,2)}

(d) {(1,2),(2,3),(3,4)}

{(1,1),(2,2),(3,3),(4,4)}
Let R={(1,2),(1,3),(2,3),(2,4),(3,1)} and S ={(2,1),(3,1),(3,2),( 4,2)} be relations K2
11.
defined on{1,2,3,4}. Find SoR and RoS.

Define Sub-Group of a Group. K1

12.
Define order of Group and Order of an element of Group. K2
13.
Define i) a permutation, ii) a symmetric group. K2
14.
Give an example of a semi-group which is not a group. K2
15.
16. Let α =( 1 3 25 )( 1 4 3 )( 2 5 ) ϵ S 5 ,Find α −1 and express it as a product of disjoint K2
−1
cycles. State whether α ∈ S 5 .

Show that every subgroup of an Abelian/Cyclic group is Normal. K2

17.
Consider the ring Z10={0 , 1 ,2 , ... , 9 } of integers modulo 10. K3
18.
(a) Find the units of Z10 .
(b) Find −3, −8, and 3−1 .
Prove that F ={ a + b √ 22 | a, b integers} is an integral domain but not a field. K3
19.
Show that R={0 , 2 , 4 , 6 , 8 } is an integral Domain under addition and K3
20.
multiplication modulo 10.
K1
21. How many vertices and how many edges do graphs have?
K2
22. How many sub graphs with at least one vertex does have?
COURSEPACK | FORMAT
 K1
23. For which values of and is is regular?
Is every zero-one square matrix that is symmetric and has zeros on the diagonal the K1
24. adjacency matrix of a simple graph?
What is the sum of the entries in a column of the adjacency matrix for an undirected K2
25. graph? For a directed graph?
Show that a connected multigraph with at least two vertices has an Euler circuit iff each K3
26. of its vertices has an even degree.
K3
27. Show that has a Hamilton circuit whenever
K2
28. What is the chromatic number of ?
Prove that the number of vertices in a full binary tree is always odd. K1
29.
Suppose that a connected planar simple graph has 20 vertices, each of degree 3. In to K3
30. how many regions does a representation of this planar graph split the plane?
State and prove Euler’s formula. K3
31.
Show that the “greater than or equal” relation (≥) is a partial ordering on the set K1
32.
of integers.
K1
33. In the poset , are the integers 3 and 9 comparable? Are 5 and 7
comparable?
Determine whether the relations represented by these zero-one matrices are K1
34.
partial orders.

a) b)

Find the dual of Poset( Z , ≥ ) . K1

35.
Draw the Hasse diagram representing the partial ordering {(a , b)∨a∣b } on K3
36.
{1 , 2 ,3 , 4 , 6 , 8 ,12 }.
Let S= {1, 2, 3, 4}. With respect to the lexicographic order based on the usual K2
37.
“less than” relation, find all pairs in S × S less than (2 , 3).
Draw the Hasse diagram for divisibility on the set{3 , 5 , 7 , 11,13 , 16 , 17 }. K3
38.
Define Lattice. K1
39.
Which elements of the poset ¿ are maximal, and which are minimal? K2
40.
Let S be a set. Determine whether there is a greatest element and a least element K2
41.
in the poset (P(S),).
Find the greatest lower bound and the least upper bound of the set {3 , 9 , 12 } and K2
42.
{1 , 2 , 4 , 5 , 10} , if they exist, in the poset¿.
Is the poset ¿ a lattice? K2
43.
K2
44. Determine whether (P(S), ) is a lattice where S is a set.
Show that every totally ordered set is a lattice. K3
45.

COURSEPACK | FORMAT
STUDENT-CENTERED LEARNING (SELF-LEARNING TOWARDS LIFE-
LONG-LEARNING)

Self-Learning (it’s a typical course-based project to be carried out by a whole class in

groups of four students each; they should exhibit higher level BTLs)

The students, in a group, are expected to conceive an idea based on the content
(objectives/outcomes) and apply the suitable knowledge to demonstrate their
learning.
A list of 30-40 project statements can be offered to the students to choose or students
can conceive their own ideas (teamwork), design and develop the
product/process/service and implement the same.

A) COURSE-BASED PROJECT (Psychomotor skills)

To enhance their skill set in the integrated course, the students are advised to
execute course-based
design projects. Some sample projects are given below:

S. No. Suggested Projects BTL

1 Game Theory: Designing interesting games and/or finding winning L6
strategies for known games. Describe the game in terms of graphs, what are
you trying to achieve or avoid?
i. What games that you know can be studied in terms of graphs? Is
Tic-Tac-Toe an example of this? What is the graph? What are
you trying to avoid? You can also study Tic-Tac-Toe
generalizations.
ii. Find out how the Game of Dim is played and study it from the
graph theory point of view.
2 Number Theory: Understand divisibility criteria. Develop divisibility L5
criteria for "nontraditional" primes, like 7 or 13. Can you explain why these
are not usually mentioned in the regular literature?
3 Scheduling Problems: When organizing a conference or event, how do L6
you schedule the talks according to participant and room restrictions? How
are final exams, spelling bee competitions, sports competitions scheduled at
your school? How do you make sure that all or must participants will be
able to attend their events or exams?
4 Power in games: Are there student elections at your school? Do you vote L6
on certain school decisions? How much power do you have in an election
where each department has one vote but some departments are larger than
others? What kind of majority is needed?
5 Matchings, SDRs, and Stable Marriage Problems: How to form teams in L6
your class according to classmates’ preferences (lists of preferences are
provided by each student)? Look for other variations on this situation.
6 Algebraic representations of graphs: Study the adjacency matrix of a L5
graph. How can you find the number of edges, the degrees, the number of
COURSEPACK | FORMAT
 triangles, etc., without drawing the graph. Just by using the entries of the
matrix.
7 Latin squares: Study Latin squares and their relationship to Sudoku. How L6
many Latin squares are there of a fixed size under certain given
restrictions? Come up with easier but still interesting Sudoku variations.

B) SELF-LEARNING THROUGH MOOCs (Cognitive Skills): Certification

https://www.coursera.org/learn/discrete-mathematics

COURSEPACK | FORMAT