Rajarshi Janak University

Faculty of Science, Technology and Engineering

Course of Study for [Link]
(Second Semester/First Year)

Course Title: Discrete Structures Course Code: CSIT 203

Nature of Course: Theory and Practical Full Marks: 60+20+20
Credit Hrs: 3 Hrs Pass Marks: 20+8+8

Course Description:
This course introduces fundamental mathematical structures essential for computer science and
information technology. It covers topics such as set theory, propositional logic, relations,
functions, graph theory, number theory, combinatorics, and proof techniques. The course
emphasizes both theoretical foundations and practical applications, including algorithms for graph
traversal, shortest paths, minimum spanning trees, and combinatorial problem-solving. Laboratory
work involves implementing these concepts using high-level programming languages (e.g.,
Python) to reinforce theoretical knowledge and develop problem-solving skills. The curriculum
prepares students to apply discrete mathematical principles in areas like algorithm design, data
structures, cryptography, and artificial intelligence.

Course Learning Objectives:By the end of this course, students will be able to:
1. Analyze sets, relations, and functions using principles like inclusion-exclusion,
equivalence relations, and closure properties.
2. Apply propositional/predicate logic to evaluate truth values, construct proofs, and resolve
quantified statements.
3. Model problems using graph theory, including shortest-path algorithms (Dijkstra),
spanning trees (Kruskal), and Euler/Hamiltonian paths.
4. Solve number-theoretic problems (GCD, modular arithmetic) and combinatorial
challenges (permutations, binomial coefficients).
5. Construct proofs using induction, contradiction, and contraposition, ensuring logical
rigor.
6. Design solutions for optimization problems, such as network flows, graph isomorphism,
and the Travelling Salesman Problem.
7. Integrate discrete mathematics with programming to simulate real-world scenarios in lab
projects.

Course Contents

Unit 1
Set Theory and Propositional Logic [8 hrs]
Set Theory: Sets and Subsets, power set and its properties, set operations, Principle of
Inclusion and Exclusion, computer Representation of sets, Fuzzy sets and Membership Function,
Fuzzy Set Operations
Logic: Introduction, Propositional Equivalences, Predicates and Quantifiers, Negation of
Quantified Statements, Nested Quantifiers, Rules of Inference and related Problems. Connectives
well-formed formula (WFF), Quantification, examples and properties of WFF into causal form,
Resolution and refutation, answer extraction and simple examples.

Unit-2
Relation and Function [6 hrs]
Relations: Relations and their Properties, N-ary Relations with Applications, Representing
Relations, Closure of Relations, Equivalence Relations, Partial Ordering, Hasse diagram, Lattice
Functions: Basic Concepts, Injective and Bijective Functions, Inverse and Composite Functions,
Graph of Functions, Functions for computer Science( Ceiling Function, Floor Function, Boolean
Function, Exponential function, logarithmic Function)

Unit-3
Mathematical Induction and Proof Techniques [8 hrs]
Induction: Introduction to Mathematical Induction, Strong Induction, Well ordering, Recursive
Definition and structural Induction, Recursively Defined Functions Recursive Algorithms,
Proving Correctness of Recursive Algorithms
Proof Techniques: Basic Terminologies, Different Method: Direct Proof, Indirect Proof, Proof
by Contradiction, Proof by contraposition, Proof of Equivalence, vacuous and Trivial Proof,
Exhaustive Proof and Proof by cases, Mistakes in Proof

Unit-4
Number Theory and Counting [12 hrs]
Introduction to Integers and Number Theory : Integers and Division, Primes and Greatest
Common Divisor, Euclidean and Extended Euclidean Algorithm, Integers and Algorithms,
Applications of Number Theory (Linear Congruencies, Quadratic Congruencies, Chinese
Remainder Theorem, Computer Arithmetic with Large Integers, one-one Matrices, Boolean
Matrix Operations.
Counting: Elementary configuration: - Permutations, and Combinations, Generating functions,
Counting Subsets of Set, Binomial Coefficients, Generalized Permutations and Combinations,
Basics, Pigeonhole Principle, Generalized Pigeonhole Principle, Lexicographical and Fike’s
ordering of Permutations, Algorithms for Lexicographical, Reverse Lexicographical and Fike’s
ordering of Permutation.
Advances in Counting: Recurrence Relations, Solving Recurrence Relations (Homogeneous and
NonHomogeneous Equations), Introduction to Divide and Conquer Relations

Unit-5
Group Theory [3 hrs]
Group, subgroup, permutation group with simple examples, cosets, normal subgroup, burn sides
theorem and its simple application, codes, prefix codes and group codes.
Unit 6 [8 hrs]
Graph Theory: Graph, Definitions and examples, Graphs diagraphs, walk, path cycle, sub graph,
complements, and graph isomorphism, vertex degree, Representation of graphs, Euler Trails and
circuits, connectivity in Graphs, Euler and Hamiltonian Paths and Circuits, Matching Theory,
Shortest Path Algorithm (Dijkstra’s Algorithm), Travelling Salesman Problem, Graph Coloring
Trees: Definition, properties and examples, Rooted trees, Tress and sorting, weighted trees, cycle
connectedness tree, computer representation of relations, relation diagraph and graphs, transitive
closer and Warshall’s Algorithm, Spanning Trees, Minimum Spanning Trees (Kruskal’s
Algorithm)
Network Flows: Graph as Models of Flow of Commodities, Flows, Maximal Flows and Minimal
Cuts, the Max Flow-Min Cut Theorem

Laboratory Work:
Laboratory works should consist of program development and testing of all the topics discussed
in theory class software’s like C, C++, MATLAB R202x., python 3.x with Numpy/Maplotlib or
any other appropriate programming language platform. Separate lab report should be submitted
for each lab applicable unit on individual [Link] list of lab experimens are:

1. Implement union, intersection, difference, power set, and Cartesian product.

2. Create and evaluate fuzzy set membership using triangular or trapezoidal functions.
3. Evaluate compound propositions and generate truth tables using user-defined input.
4. Check equivalence of two logical expressions using truth tables.
5. Analyze binary relations for reflexive, symmetric, and transitive properties.
6. Check if a given function is injective, surjective, or bijective.
7. Implement recursive functions (e.g., Fibonacci) and trace them to demonstrate induction.
8. Compute GCD and modular inverses.
9. Efficiently compute ab mod m using recursion or iterative methods.
10. Generate all permutations of a set and sort them lexicographically.
11. Compute C(n,k)C(n, k)C(n,k) using recursion and Pascal’s triangle.
12. Find the shortest path from a source node to all others.
13. Generate MST from a weighted graph using Kruskal's algorithm.
14. Compute transitive closure of a directed graph.

Text Books/Reference Books:

1. K. H. Rosen, Discrete Mathematics and Its Applications, 7th ed. Chennai: McGraw Hill
Education Pvt. Ltd.
2. J.-P. Tremblay and R. Manohar, Discrete Mathematical Structures with Applications to
Computer Science. New York: McGraw Hill.
3. C. L. Liu, Elements of Discrete Mathematics, International ed.
4. N. S. Deo, Graph Theory with Applications to Computer Science. New Delhi: PHI.
5. B. Kolman, R. C. Busby, and S. Ross, Discrete Mathematical Structures. New Delhi:
Pearson.
6. E. S. Page and L. B. Wilson, An Introduction to Computational. Cambridge: Cambridge
University Press.
7. [7] R. P. Grimaldi, Discrete and Combinatorial Mathematics, 5th ed. New Delhi: Pearson
Education.