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.

Metadata

Proposing Faculty: Department: Computer Science and Engineering Programme: B.Tech Proposing date: Approved date: Proposal type: Offerings: