Course Plan

CS 202 Discrete Structures L T P C
B.Tech (CSE) Third Semester (Core) 3 1 0 4

Unit-1 Logic: Propositional logic and its applications; Propositional equivalences;
Predicates and Quantifiers; Rules of inference; Introduction to Proofs;
Proof Methods; Proof by Mathematical Induction (Weak and Strong).
Unit-2 Set theory: Sets, operations on sets, cardinality, inductive definition of
sets and proof by induction; Relations, representation of relations,
properties of relations, equivalence relations and partitions; Partial
orderings; Posets; Well-ordered sets.

Unit-3 Functions: Mappings; Injection and Surjection; Composition of functions;

Inverse functions; Special functions; recursive function theory.

Unit-4 Algebraic Structures: Definition and elementary properties of groups;
semigroups; monoids; rings; fields, vector spaces; lattices and Boolean
Algebra.

Unit-5 Elementary combinatorics: Basic Counting Principles; Permutations and
Combinations; Binomial Coefficients and Identities; Generalized
Permutations and Combinations; Sterling’s number of the second kind;
Pigeon-hole Principle and its application; Inclusion-Exclusion Principle
and its application; Recurrence Relations; Solving Linear Recurrence
Relations; Generating Functions; Catalan Numbers; Fibonacci numbers.
Unit-6 Number Theory: Divisibility and Modular Arithmetic; Integer
Representations and Algorithms; Prime numbers and related
Theorems; Greatest Common Divisors; Euclid’s Algorithm; Solving
Congruence; Applications of Congruence, Fermat’s Little Theorem, The
Chinese Remainder Theorem; Applications in Cryptography.

Books:
1. K. H. Rosen , Discrete Mathematics and Applications, TMH
2. C. L. Liu, D. P. Mohapatra, Elements of Discrete Mathematics , McGraw-Hill
3. J. L. Mott, A. Kandel, T. P. Bake, Discrete Mathematics for Computer Scientists and
Mathematicians , PHI
4. J. P. Tremblay, R. Manohar, Discrete Mathematical Structures with Applications to
Computer Science, McGraw-Hill

Course Plan:
Detail plan for Unit 1.
Periods Topics / Sub – Topics covered
1 Propositional Logic and its Applications
1 Propositional equivalences
1 Predicates and Quantifiers
1 Rules of inference
1 Introduction to Proofs
1 Proof Methods
1 Proof by Mathematical Induction

Detail plan for Unit 2.
Periods Topics / Sub – Topics covered
1 Sets, operations on sets, cardinality
1 Inductive definition of sets and proof by induction
1 Relations, representation of relations, properties of relations
1 Equivalence relations and partitions
2 Partial orderings; Posets; Well-ordered sets.

Detail plan for Unit 3.
Periods Topics / Sub – Topics covered
1 Mappings; Injection and Surjection; Composition of functions; Inverse functions;
1 Recursive function theory.

Detail plan for Unit 4.
Periods Topics / Sub – Topics covered
2 Definition and elementary properties of groups; semigroups; monoids; rings; fields,
1 Vector spaces; lattices and Boolean Algebra.

Detail plan for Unit 5.
Periods Topics / Sub – Topics covered
1 Basic Counting Principles
1 Permutations and Combinations
1 Binomial Coefficients and Identities
1 Generalized Permutations and Combination
1 Sterling’s number of the second kind; Pigeon-hole Principle and its application
1 Inclusion-Exclusion Principle and its application
1 Recurrence Relations
2 Generating Functions; Catalan Numbers; Fibonacci numbers.

Detail plan for Unit 6.
Periods Topics / Sub – Topics covered
2 Divisibility and Modular Arithmetic
1 Integer Representations and Algorithms; Prime numbers and related Theorems
1 Greatest Common Divisors; Euclid’s Algorithm
1 Solving Congruence Applications of Congruence
1 Fermat’s Little Theorem, The Chinese Remainder Theorem
2 Applications in Cryptography

Evaluation Plan
1. Mid-30 marks
2. End-50 marks
3. Minor-10 marks
4. Assignment-10 marks

Class Notes & PPTs

1. - PPT