Discrete Mathematics (MATH-206/5111)

WHY STUDY DISCRETE MATHEMATICS? There are several important reasons for studying discrete mathemat - ics. First, through this course you can develop your mathematical maturity: that is, your ability to understand and create mathematical arguments. You will not get very far in your studies in the mathematical sciences without these skills. Second, discrete mathematics is the gateway to more advanced courses in all parts of the mathematical sciences. Discrete mathematics provides the mathematical foundations for many compu- ter science courses, including data structures, algorithms, database theory, automata theory, formal langu-  ages, compiler theory, computer security, and operating systems. Students find these courses much more difficult when they have not had the appropriate mathematical foundations from discrete mathematics.

Learning Outcomes: On completion of Course, the student should:

  • Understand the notion of mathematical thinking, mathematical proofs, and algorithmic thinking, and be able to apply them in problem solving.
  • Be able to use effectively algebraic techniques to analyse basic discrete structures and algorithms.
  • Understand some basic properties of graphs and related discrete structures, and be able to relate these to practical examples.

Contents

  1. Counting methods: Basic methods: product,
  2. inclusion-exclusion formulae.
  3. Permutations and combinations.
  4. Recurrence relations and their solutions
  5. Generating functions.
  6. Double counting. Applications.
  7. Pigeonhole principle, applications.
  8. Relations: Binary relations, n-ary Relations.
  9. Closures of relations.
  10. Composition of relations, inverse relation
  11. Graphs: Graph terminology.
  12. Representation of graphs. Graphs isomorphism.
  13. Algebraic methods: the incidence matrix.
  14. Connectivity, Eulerian and Hamiltonian paths.
  15. Shortest path problem.
  16. Trees and spanning trees.
  17. Complete graphs and bivalent graphs.

Recommended Books

  1. Kenneth H. Rosen, Discrete athematics and its application, (McGraw Hill, New York, 2019).
  2. Parthasarathy K.R. Basic Graph Theory, (McGraw-Hill, 1994).

Suggested Books

  1. Tucker A. Applied Combinatorics, John Wiley and Sons, (Inc New York, 2002).
  2. Diestel R. Graph Theory, 4th edition, ( Springer- Verlag, New York, 2010).
  3. Brigs N.L. Discrete Mathematics, (Oxford University Press, 2003

RESEARCH PROJECT /PRACTICALS/LABS/ASSIGNMENTS

Exercises of the relevant topics given in the suggested book as assignments. Moreover, students have to develop some computer programs of the terminologies/concepts/examples learned during the lecturers.

Assessment Criteria

Sessional: 20 (Presentation / Assignment 10, Attendance 05, Quiz 05)

Mid-Term Exam: 30

Final-Term Exam: 50

Key Dates and Time of Class Meeting

Tuesday/Thurseday                                                                             11:00 am-12:30 pm

Wednesday/Thurseday                                                                        14:00 pm-15:30 pm

Commencement of Classes                                                   January 13, 2020

Mid Term Examination                                                            March 09-13, 2020

Final Term Examination                                                          May 04-08, 2020

Declaration of Result                                                              May 19, 2020

Course Material

Other Courses by Dr. Ahmad Muhammad Mumtaz