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

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

Text Books:

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

References:

  1. Discrete Mathematics: Elementary and Beyond by László Lovász, József Pelikán, Katalin Vesztergombi, Springer 2003, ISBN-13: 978-0387955858.
  2. 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