Guidelines for [Link].
(H) Computer Science Semester II (NEP UGCF 2022)
Discrete Mathematical Structures
DSC05
(Effective from Academic Year 2024-25)
S. No. Topic Reference Contents Hours
1 Unit 1 - Sets, Relations [2] 2.1 (upto example 21), 2.2, 2.3, 2.4: 2.4.1, 7
and Functions 2.4.2, 2.4.5
8.5
9.1, 9.3: 9.3.1, 9.3.2, 9.4: 9.4.1, 9.4.2, 9.4.3,
9.4.4, 9.5: 9.5.1, 9.5.2, 9.6: 9.6.1, 9.6.2,
9.6.3
2 Unit 2 - Logic and Proofs [2] 1.1, 1.2, 1.3 (upto 1.3.5), 1.4 (upto 1.4.3), 11
1.6 (upto 1.6.6), 1.7
5.1: 5.1.1 to 5.1.7 (upto page 343)
3 Unit 3 - Number Theory [2] 4.1, 4.2, 4.3: 4.3.1, 4.3.2, 4.3.3, 4.3.6, 4.3.7 7
4 Unit 4 - Combinatorics [1] 2.1 to 2.4 5
[2] 6.2 (upto 6.2.1)
5 Unit 5 - Graphs and Trees [2] 10.1 (upto page 676), 10.2: 10.2.1, 10.2.2, 10
10.2.3, 10.3 (excluding algorithms and
application of isomorphism), 10.4: 10.4.1,
10.4.2, 10.4.3, 10.4.4, 10.4.5, 10.5: 10.5.1,
10.5.2, 10.5.3, 10.6: 10.6.1, 10.7: 10.7.1,
10.7.2
11.1: 11.1.1, 11.1.3: Theorem 2 only with
proof
6 Unit 6 - Recurrences [1] 8.1, 8.2 5
9.1, 9.2, 9.3
Note:
1. Exclude proofs of theorems, lemmas and corollaries.
2. Guidelines have been prepared according to soft copy of reference [2].
3. Practical implementation to be done in either Python or C++.
References
1. Liu, C.L., Mohapatra, D.P. Elements of Discrete Mathematics: A Computer Oriented Approach,
4th edition, Tata McGraw Hill, 2017.
2. Rosen, K.H., Discrete Mathematics and Its Applications, 8th edition (soft copy), Mc Graw Hill,
2018.
Practical List
1. Create a class SET. Create member functions to perform the following SET operations:
a. is member: check whether an element belongs to the set or not and return
value as true/false.
b. powerset: list all the elements of the power set of a set.
c. subset: check whether one set is a subset of the other or not.
d. union and intersection of two Sets.
e. complement: assume universal set as per the input elements from the user.
f. set difference and symmetric difference between two sets.
g. cartesian product of sets.
Write a menu driven program to perform the above functions on an instance of the SET
class.
2. Create a class RELATION, use Matrix notation to represent a relation. Include member
functions to check if the relation is Reflexive, Symmetric, Anti-symmetric, Transitive. Using
these functions check whether the given relation is: Equivalence or Partial Order relation or
None
3. Write a Program that generates all the permutations of a given set of digits, with or without
repetition.
4. For any number n, write a program to list all the solutions of the equation x1 + x2 + x3 + ...+
xn = C, where C is a constant (C<=10) and x1, x2, x3,...,xn are nonnegative integers, using
brute force strategy.
5. Write a Program to evaluate a polynomial function. (For example store f(x) = 4n2 + 2n + 9
in an array and for a given value of n, say n = 5, compute the value of f(n)).
6. Write a Program to check if a given graph is a complete graph. Represent the graph using
the Adjacency Matrix representation.
7. Write a Program to accept a directed graph G and compute the in-degree and outdegree of
each vertex.