**Code:**CS5013 |

**Category:**PMT |

**Credits:**3-0-0-3

# Course Objective

This is a course intended to prepare starting graduate students with a selected set of topics from Discrete Mathematics which play a major role in Theoretical Computer Science. The emphasis will be on laying these foundations as rigorously as possible.

# Course Contents

**Naive Set Theory**: Cardinality of sets, SchrĂ¶derâ€“Bernstein Theorem. Uncountable sets. Diagonalisation, Cantorâ€™s Theorem. (10 lectures)

**Number Theory**: Induction, and Well Ordering Principle. Proofs using Induction and Well Ordering Principle. BĂ©zout's identity. Euclidâ€™s Algorithm, Structural Induction. Fermatâ€™s Little Theorem, Eulerâ€™s theorem, Modular Arithmetic. Chinese Remainder Theorem. (16 lectures)

**Introduction to First Order Logic** Syntax of First Order Logic, Scope and Binding. Semantics. Models, First Order Calculus, Soundness and Completeness of First Order Calculus, Compactness and its Applications. (16 lectures)

# Learning Outcomes:

After successful completion of this course, a student will be able to

- Follow a rigorous mathematical proof and identify gaps in reasoning if any.
- Reason about sizes of infinite sets.
- Apply standard proof techniques to prove statements about simple mathematical structures.
- Prove properties of recursively defined structures using structural induction.

# Text Books:

- Discrete Mathematics (2nd edition) by Norman L. Biggs, OUP, 2002, ISBN-13: 978-0198507178.
- Part II (Logic) of the Computational Complexity book by Christos H. Papadimitrou, Pearson, 1993, ISBN-13: 9780201530827.

# References:

- Discrete Mathematics: Elementary and Beyond by LĂˇszlĂł LovĂˇsz, JĂłzsef PelikĂˇn, Katalin Vesztergombi, Springer 2003, ISBN-13: 978-0387955858.
- Discrete Mathematics and Applications by Kenneth Rosen, 7th Edition, McGraw-Hill Education 2012, ISBN-13: 978-0073383095.

# Past Offerings

- Offered in Aug-Nov, 2023 by Srimanta Bhattacharya
- Offered in Aug-Dec, 2022 by Krithika Ramaswamy
- Offered in Jul-Dec, 2021 by Deepak
- Offered in Jul-Dec, 2020 by Krithika

# Course Metadata

Item | Details |
---|---|

Course Title | Topics in Discrete Mathematics |

Course Code | CS5013 |

Course Credits | 3-0-0-3 |

Course Category | PMT |

Proposing Faculty | Jasine Babu |

Approved on | Senate 11 of IIT Palakkad |

Course status | old |