Course Code: MATH-206

Discrete Mathematics

Prerequisite(s): Mathematics at Intermediate Level

Credit Hours: 3+0

Objectives of course:

Discrete Mathematics is study of distinct, un-related topics of mathematics; it embraces topics from early stages of mathematical development and recent additions to the discipline as well. The present course restricts only to counting methods, relations and graphs. The objective of the course is to inculcate in the students the skills that are necessary for decisionmaking in non-continuous situations.

Course Contents:

Counting methods: Basic methods: product, inclusion-exclusion formulae. Permutations and combinations.Recurrence relations and their solutions.Generating functions.Double counting.Applications. Pigeonhole principle, applications. Relations: Binary relations, n-ary Relations. Closures of relations.Composition of relations, inverse relation. Graphs: Graph terminology. Representation of graphs.Graphs isomorphism. Algebraic methods: the incidence matrix. Connectivity, Eulerian and Hamiltonian paths.Shortest path problem.Trees andspanning trees. Complete graphs and bivalent graphs.

Recommended Books:

1. Bollobas, B. Graph Theory, Springer Verlag, New York, 1979.

2. Parthasarathy K.R. Basic Graph Theory, McGraw-Hill, 1994.

3. Rosen K.H. Discrete Mathematics and its Application, McGraw-Hill, 6th edition, 2007.

4. Kolman B., Busby R.C., Ross S.C. Discrete Mathematical Structures, Prentice-Hall of India, New Delhi, 5th edition, 2008.

5. Tucker A. Applied Combinatorics, John Wiley and Sons, Inc New York, 2002.

6. Diestel R. Graph Theory, 4th edition, Springer- Verlag, New York, 2010.

7. Brigs N.L. Discrete Mathematics, Oxford University Press, 2003

8. Ross K.A., WrightC.R.B.. Discrete Mathematics, Prentice Hall, New Jersey, 2003.

**RESEARCH PROJECT**

*N/A*

**ASSESSMENT CRITERIA**

Mid exam: 30

Sessional: 20

Project: --

Assignments: 10

Presentation: 10

Final exam: 50

Total: 100

**RULES AND REGULATIONS**

*75% attendance is compulsory to appear in Final Term exam.*