Course Details
Subject {L-T-P / C} : MA5251 : Discrete Mathematics { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Dr. Hiranmoy Pal
Syllabus
The language of sets: Concept of a set, Operations with sets, cardinality of a set, recursively defined sets.
Functions and Matrices: Concept of a function, Special functions, Properties of functions, pigeonhole principle, Composition of functions, Matrices.
Induction and algorithms: Division algorithm, Divisibility properties, Mathematical Induction, growth of functions.
Recursion: Recursively defined functions, Solving recurrence relations, Generating functions, Recursive algorithms.
Combinatorics and Discrete probability: Fundamental counting principles, Permutations, derangements, Combinations, Permutations and combinations with repetitions, binomial theorem, generalized inclusion and exclusion principle, Discrete probability.
Relations: Relations and digraphs, Properties of relations, Operations on relations, connectivity relations, Equivalence relations, Partial and total orderings.
Graphs: Paths, cycles and circuits, Eulerian and Hamiltonian graphs, Planner graphs, graph colouring.
Course Objectives
- To learn basic concepts of sets, relations, functions and matrices.
- To introduce the basic counting principles, binomial theorem, generalized inclusion and exclusion principle and discrete probability.
- To learn principle of mathematical induction, Euclid's division algorithm, and to study methods to solve recurrence relations.
- To have a brief introduction to graph theory and its applications.
Course Outcomes
CO1: Students become familiar with the basic tools in Mathematics, such as, sets, relations, functions and matrices. <br />CO2: Students learn the basic counting principles and their applications. They gather a deep understanding about few tools, such as, Principle of Mathematical Induction, Euclid's Division Algorithm and solvability of Diophantine equations. <br />CO3: Students study the recurrence relations and various methods to solve them. <br />CO4: Students become familiar with the basics of graph theory and its applications.
Essential Reading
- R. P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Pearson , 5th Edition, 2019
- K. H. Rosen, Discrete Mathematics and its Applications, McGraw Hill , 7th Edition, 2011
Supplementary Reading
- J. P. Tremblay, R. Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw Hill , 1st Edition
- D. B. West, Introduction to Graph Theory, Pearson Education India , 2nd Edition