Course Type | Course Code | No. Of Credits |
---|---|---|

Foundation Core | SUS1MA512/SUS1MA532 | 4 |

**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% |

**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.