Note: This syllabus is common for 

• R18 - B.TECH II Year II Sem. - CSE, IT

CS401PC: DISCRETE MATHEMATICS

B.TECH II Year II Sem. L T P C

3 0 0 3

Prerequisites: An understanding of Mathematics in general is sufficient.

Course Objectives

• Introduces the elementary discrete mathematics for computer science and engineering.
• Topics include formal logic notation, methods of proof, induction, sets, relations, graph theory, permutations and combinations, counting principles; recurrence relations and generating functions.

Course Outcomes:

• Ability to understand and construct precise mathematical proofs
• Ability to use logic and set theory to formulate precise statements
• Ability to analyze and solve counting problems on finite and discrete structures
• Ability to describe and manipulate sequences
• Ability to apply graph theory in solving computing problems

UNIT - I

The Foundations: Logic and Proofs: Propositional Logic, Applications of Propositional Logic, Propositional Equivalence, Predicates and Quantifiers, Nested Quantifiers, Rules of Inference, Introduction to Proofs, Proof Methods and Strategy.

UNIT - II

Basic Structures, Sets, Functions, Sequences, Sums, Matrices and Relations Sets, Functions, Sequences & Summations, Cardinality of Sets and Matrices Relations, Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations, Closures of Relations, Equivalence Relations, Partial Orderings.

UNIT - III

Algorithms, Induction and Recursion: Algorithms, The Growth of Functions, Complexity of Algorithms

Induction and Recursion: Mathematical Induction, Strong Induction and Well-Ordering, Recursive Definitions and Structural Induction, Recursive Algorithms, Program Correctness

UNIT - IV

Discrete Probability and Advanced Counting Techniques: An Introduction to Discrete Probability, Probability Theory, Bayes’ Theorem, Expected Value and Variance

Advanced Counting Techniques: Recurrence Relations, Solving Linear Recurrence Relations, Divide-and-Conquer Algorithms and Recurrence Relations, Generating Functions, Inclusion- Exclusion, Applications of Inclusion-Exclusion

UNIT - V

Graphs: Graphs and Graph Models, Graph Terminology and Special Types of Graphs, Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Shortest-Path Problems, Planar Graphs, Graph Coloring.

Trees: Introduction to Trees, Applications of Trees, Tree Traversal, Spanning Trees, Minimum Spanning Trees

TEXT BOOK:

1. Discrete Mathematics and its Applications with Combinatorics and Graph Theory- Kenneth H Rosen, 7th Edition, TMH.

REFERENCES BOOKS:

1. Discrete Mathematical Structures with Applications to Computer Science-J.P. Tremblay and R. Manohar, TMH,
2. Discrete Mathematics for Computer Scientists & Mathematicians: Joe L. Mott, Abraham Kandel, Teodore P. Baker, 2nd ed, Pearson Education.
3. Discrete Mathematics- Richard Johnsonbaugh, 7Th Edn., Pearson Education.
4. Discrete Mathematics with Graph Theory- Edgar G. Goodaire, Michael M. Parmenter.
5. Discrete and Combinatorial Mathematics - an applied introduction: Ralph.P. Grimald, 5th edition, Pearson Education.