Discrete Mathematics

Course TypeCourse CodeNo. Of Credits
Foundation CoreSUS1MA512/SUS1MA5324

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:

 S.No Assessment Date/period in which Assessment will take place Weightage 1 Class test End August 10% 2 Mid Semester Exam End September/ early October 25% 3 Tut/ Home Assignments Throughout the semester 15% 4 Presentation/ Viva End October/ early November 15% 5 End Semester Exam As per AUD Academic Calendar 35%