Discrete Mathematics

Type of Course:

• Compulsory Yes (Cohort BA (H) Mathematics)
• Elective Yes (Cohort BA (H) other than Mathematics)

Course Coordinator and Team: Ramneek Khassa (CC) and Kranti Kumar

Email of course coordinator: ramneek[at]aud[dot]ac[dot]in

Pre-requisites: Mathematics of the 10 + 2 level

Aim: The objective of this course is to familiarise the concept of the base step and the recursive or inductive step in applied problems and give a recursive and a non-recursive definition for an algorithm, principle of inclusion and exclusion, and also gives an introductory idea of graph theory.

Brief description of modules/ Main modules:

The following topics will be covered in the course as described below.

Part I: The Principle of Inclusion-Exclusion, the addition and multiplication rules, the Pigeonhole principle, Recurrence relations, Solving recurrence relations, Fibonnacci sequences & properties, Partition numbers, Algorithms, searching and sorting.

Part II : Definition and properties of Graphs, Pseudograph, Complete graph, Bipartite graph, Isomorphism of graphs, Eulerian circuits, Hamiltonian cycle, Adjacency matrix, Weighted graph, Travelling salesman problem, shortest path, Dijkstra’s algorithm, Floyd Warshall algorithm, Trees, Spanning trees, Minimum spanning tree, Planar graph, Euler formula, Chromatic numbers.

Refererences:

• Edgar G. Goodaire and Michael M. Parmenter, Discrete Mathematics with graph theory, E.G Goodaire and M.M Parmenter, 3rd edition, PHI.
• R. A. Brualdi, Introductory Combinatorics, 5th edition, Pearson, 2010.
• N. L. Biggs, Discrete Mathematics, Oxford University Press, 2003.

Tentative Assessment schedule with details of weightage:

Reading List:

• Edgar G. Goodaire and Michael M. Parmenter, Discrete Mathematics with graph theory, 3rd edition, PHI.
• R. A. Brualdi, Introductory Combinatorics, 5th edition, Pearson, 2010.
• N. L. Biggs, Discrete Mathematics, Oxford University Press, 2003.