JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Pre-requisites

An understanding of Math in general is sufficient.

Course Objectives

To learn

• 1. Introduces the elementary discrete mathematics for computer science and engineering.
• 2. 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

After learning the contents of this paper the student must be able to

• 1. Ability to understand and construct precise mathematical proofs.
• 2. Ability to use logic and set theory to formulate precise statements.
• 3. Ability to analyze and solve counting problems on finite and discrete structures.
• 4. Ability to describe and manipulate sequences.
• 5. 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 BOOKS:

• 1. Discrete Mathematical Structures with Applications to Computer Science: J.P. Tremblay, R. Manohar, McGraw-Hill, 1st ed.
• 2. Discrete Mathematics for Computer Scientists & Mathematicians: Joe l. Mott, Abraham Kandel, Teodore P. Baker, Prentis Hall of India, 2nd ed.

REFERENCES:

• 1. Discrete and Combinatorial Mathematics - an applied introduction: Ralph.P. Grimald, Pearson education, 5th edition.
• 2. Discrete Mathematical Structures: Thomas Kosy, Tata McGraw Hill publishing co.