### Discrete Mathematics-S.E(Computer Engineering:2019)-SCIKEEDA GUIDE

##
__Discrete Mathematics -Paper Pattern__

### Course Objectives:

####
- To use appropriate set, function and relation models to understand practical examples, and
interpret the associated operations and terminologies in context.

- Determine number of logical possibilities of events.

- Learn logic and proof techniques to expand mathematical maturity.

- Formulate problems precisely, solve the problems, apply formal proof techniques, and
explain the reasoning clearly.

### Course Outcomes:

On completion of the course, student will be able to–

####
- Solve real world problems logically using appropriate set, function, and relation models
and interpret the associated operations and terminologies in context.

- Analyze and synthesize the real world problems using discrete mathematics.

##

Course Contents
__Unit I :__
__Set Theory and Logic -09 Hours __

Discrete Mathematics, Significance of Discrete Mathematics in Computer Engineering.
- Sets–
NaÃ¯ve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Need for Sets, Representation of
Sets, Set Operations, cardinality of set, principle of inclusion and exclusion.

- Types of Sets –
Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably
Infinite Sets. Introduction to bounded and unbounded sets and multiset. Countability of Rational
Numbers Using Cantor Diagonalization Argument, power set.

- Propositional Logic- logic,
Propositional Equivalences, Application of Propositional Logic-Translating English Sentences,
Proof by Mathematical Induction and Strong Mathematical Induction.

__ Unit II__
__ Relations and Functions -09 Hours __
- Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations ,
Closures of Relations, Equivalence Relations, Partial Orderings, partitions, Hasse Diagram,
Lattices, Chains and Anti-Chains, Transitive Closure and Warshall‘s Algorithm, n-Ary Relations
and their Applications.
- Functions- Surjective, Injective and Bijective functions, Inverse Functions and Compositions of
Functions, The Pigeonhole Principle.

__Unit III __
__Counting -09 Hours __

The Basics of Counting, rule of Sum and Product, Permutations and Combinations, Binomial
Coefficients and Identities, Generalized Permutations and Combinations, Algorithms for
generating Permutations and Combinations.

__Unit IV __
__Graph Theory -09 Hours __

Graphs and Graph Models, Graph Terminology and Special Types of Graphs, Representing
Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Single source shortest
path- Dijkstra's Algorithm, Planar Graphs, Graph Colouring. Case Study- Web Graph, Google
map.

__Unit V __
__Trees -09 Hours __

Introduction, properties of trees, Binary search tree, decision tree, prefix codes and Huffman
coding, cut sets, Spanning Trees and Minimum Spanning Tree, Kruskal‘s and Prim‘s algorithms,
The Max flow- Min Cut Theorem (Transport network). Case Study- Game Tree, Mini-Max Tree.

__Unit VI __
__Algebraic Structures and Coding Theory -09 Hours__

The structure of algebra, Algebraic Systems, Semi Groups, Monoids, Groups, Homomorphism and
Normal Subgroups, and congruence relations, Rings, Integral Domains and Fields, coding theory,
Polynomial Rings and polynomial Codes, Case Study- Brief introduction to Galois Theory –Field
Theory and Group Theory.

__Unit I :__

__Set Theory and Logic -09 Hours__

- Sets– NaÃ¯ve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Need for Sets, Representation of Sets, Set Operations, cardinality of set, principle of inclusion and exclusion.

- Types of Sets – Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets. Introduction to bounded and unbounded sets and multiset. Countability of Rational Numbers Using Cantor Diagonalization Argument, power set.

- Propositional Logic- logic, Propositional Equivalences, Application of Propositional Logic-Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction.

__Unit II__

__Relations and Functions -09 Hours__

- Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations , Closures of Relations, Equivalence Relations, Partial Orderings, partitions, Hasse Diagram, Lattices, Chains and Anti-Chains, Transitive Closure and Warshall‘s Algorithm, n-Ary Relations and their Applications.
- Functions- Surjective, Injective and Bijective functions, Inverse Functions and Compositions of Functions, The Pigeonhole Principle.

__Unit III__

__Counting -09 Hours__

__Unit IV__

__Graph Theory -09 Hours__

__Unit V__

__Trees -09 Hours__

__Unit VI__

__Algebraic Structures and Coding Theory -09 Hours__

##

REFERENCE BOOKS

1. Kenneth H. Rosen, ―Discrete Mathematics and its Applications‖, Tata McGraw-Hill, ISBN
978-0-07-288008-3, 7th Edition.

2. C. L. Liu, ―Elements of Discrete Mathematics‖, TMH, ISBN 10:0-07-066913-9.

3. Bernard Kolman, Robert C. Busby and Sharon Ross, ―Discrete Mathematical Structures‖,
Prentice-Hall of India /Pearson, ISBN: 0132078457, 9780132078450.

4. N. Biggs, ―Discrete Mathematics‖, 3rd Edition, Oxford University Press, ISBN 0 –19
850717 – 8.

5. Narsingh Deo, ―Graph with application to Engineering and Computer Science‖, Prentice
Hall of India, 1990, 0 – 87692 – 145 –

6. Dr. K. D. Joshi, ―Foundations of Discrete Mathematics‖, New Age International Limited,
Publishers, January 1996, ISBN: 8122408265, 9788122408263

7. C.D. Cantrell, ―Modern Mathematical Methods for Engineers‖, Cambridge University
Press, ISBN-0521670497

8. Eric Gossett, ―Discrete Mathematical Structures with Proofs‖, Wiley India Ltd,
ISBN:978-81-265-2758-8.

9. Sriram P & Steven S, ―Computational Discrete Mathematics‖, Cambridge University
Press, ISBN 13: 978-0-521-73311-3.

### FREE PAID E-BOOKS ::

(CLICK THE TITLE BUTTON TO DOWNLOAD E-BOOKS)