CA-C1T: DISCRETE STRUCTURES
Total Teaching Hours: 48 No. of Hours / Week: 03
UNIT – I [12 Hours]
Set Theory and Logic: Fundamentals of Set theory, Set Operations and the Laws of Set Theory, Counting and
Venn Diagrams, Cartesian Products and Relations, Functions–One-to-One, Onto Functions, Function
Composition and Inverse Functions. Mathematical Induction, The well ordering principle, Recursive
Definitions, Structural Induction, Recursive algorithms. Fundamentals of Logic, Propositional Logic, Logical
Connectives and Truth Tables, Logic Equivalence, Predicates and Quantifiers.
UNIT – II [12 Hours]
Counting and Relations: Basics of counting, Pigeonhole Principle, Permutation and Combinations, Binomial
coefficients. Recurrence relations, Modeling with recurrence relations with examples of Fibonacci numbers
and the tower of Hanoi problem. Divide and Conquer relations with examples (no theorems). Definition and
types of relations, Representing relations using matrices and digraphs
UNIT – III [12 Hours]
Matrices: Definition, order of a matrix, types of matrices, operations on matrices, determinant of a matrix,
inverse of a matrix, rank of a matrix, linear transformations, applications of matrices to solve system of
linear equations.
UNIT – IV [12 Hours]
Graph Theory: Graphs: Introduction, Representing Graphs, Graph Isomorphism, Operations on graphs.
Trees: Introduction, Applications of Trees, Tree Traversal, Spanning Trees, Minimum Spanning Trees, Prim’s
and Kruskul’s Algorithms. Connectivity, Euler and Hamilton Paths, Planar Graphs. Directed graphs:
Fundamentals of Digraphs, Computer Recognition – Zero-One Matrices and Directed Graphs, Out-degree,
in-degree, connectivity, orientation, Eulerian and Hamilton directed graphs, tournaments.
Text Books:
1. Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, 5thEdition, Pearson Education, 2004.
2. C. L. Liu: Elements of Discrete Mathematics, Tata McGraw-Hill, 2000.
3. F. Harary: Graph Theory, Addition Wesley, 1969.
4. Richard Bronson, Schaum’s Outline of Matrix Operations, McGraw-Hill publications, 2nd Edition, 2011
Reference Books:
1. Kenneth H Rosen. Discrete Mathematics and its Applications, McGraw-Hill publications, 7th edition,
2007.
2. J. P. Tremblay and R.P. Manohar. Discrete Mathematical Structures with applications to Computer
Science, Mc Graw Hill Ed. Inc. 1975.
3. Charles G Cullen. Matrices and Linear Transformations, Dover Publications Inc., Second Edition, 1990
Web Resources:
1. https://www.my-mooc.com/en/categorie/mathematics
2. http://www.nptelvideos.in/2012/11/discrete-mathematical-structures.html
3. https://ocw.mit.edu/courses/mathematics/
