# MTH211: Discrete Mathematics (Spring 2020)

## Course Objectives:

Discrete Mathematics is branch of Mathematics which deals with discrete structures like logic. sequences, graphs, relations in contrast to Calculus. where we enjoy the continuity of functions and the set of real numbers. This course is introduction to discrete structures which are not the part of main stream courses. Discrete Mathematics has applications in Computer Science. Economics and Decision Making etc. This course will help the student to understand the basic logical system, counting principles, relations. solution of recurrence relation. solution of the problems which can be translated in simple diagrams namely Graphs and Trees and the comparison between two algorithms in the sense of efficiency. The objective of the course is to inculcate in student the skills required for decision making in non- continuous situations.

## Course Contents:

Logical forms and equivalences, conditional statements, validity of arguments, quantiﬁers, multiplication rule, inclusion-exclusion formulae, permutations and combinations, pigeonhole principle, binary relations. n-ary relations, equivalence relations, partial order relations, recursive relation, solution of recurrence relation by iteration and by root method, graphs .matrix representations of graphs, graphs isomorphism, trees, connectivity, Eulerian and Hamiltonian paths, spanning trees and shortest path problem. revisiting the graphs of power function, ﬂoor function, increasing and decreasing functions, big 0, little 0 and w notations, orders of polynomial functions, orders of simple algorithms, efﬁciency of an algorithm, exponential and logarithmic orders, efﬁciency of binary search algorithm.

## Schedule

- Wednesday,1330-1500 , CR-1
- Thursday, 1000-1130, CR-1

## Notes, assignments, quizzes & handout

Please download PDF files of the notes given below. To view PDF files, there must be PDF Reader (Viewer) installed on your PC or mobile or smartphone. It can be downloaded from Software section or a user viewing on Android Smartphone may consider EBookDroid to view PDF on their smartphone.

#### Assignment

## Recommended book

- K.H. Rosen, Discrete Mathematics and its Application, MeGraw-Hill, 6th edition. 2007.
- K.R. Parthasarathy, Basic Graph Theory. McGraw-Hill. 1994.
- B. Bollobas, Graph Them-y. Springer Verlag. New York, 1979.
- B. Kolman, R.C. Busby, S.C. Ross, Discrete Mathematical Structure, Prentice-Hall of India, New Delhi, 5th Edition. 2008.
- A. Tucker, Applied Combinatorics, John Wiley and Sons. Inc New York, 2002.
- R. Diestel, Graph Theory, 4th edition, Springer-Verlag. New York. 2010.
- N.L. Brigs, Discrete Mathematics, Oxford University Press. 2003
- K.A. Ross, C.R.B. Wright, Discrete Mathematics, Prentice Hall. New Jersey, 2003.