JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

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 understand and describe algebraic structures
• 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

Algebraic Structures: Introduction, Algebraic Systems, Semi groups and Monoids, groups, Abelian groups, Lattices as Partially Ordered Sets, Boolean Algebra. 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.

REFERENCE 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, 7ThEdn., 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.