Course Contents

Logic and Set Theory: Introduction to proofs, logical formulas - propositional and predicate. Sets, functions, relations, equivalences and partial orders. Cardinality of sets, Schröder–Bernstein Theorem. Uncountable sets. Diagonalization, Cantor’s Theorem. [15 lectures + 5 tutorial sessions]

Discrete Probability: Events and probability spaces, conditional probability, law of total probability. Independence. Random variables: independence, distribution functions, expectations. Linearity of Expectation. [15 lectures + 5 tutorial sessions]

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. [12 lectures + 4 tutorial sessions]

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.
  5. Calculate probabilities and discrete distributions for simple combinatorial processes; calculate expectations.

Textbooks

  1. Discrete Mathematics (2nd edition) by Norman L. Biggs, OUP, 2002, ISBN: 978-0198507178.
  2. Probability and Computing by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2017, ISBN: 978-1107154889.
  3. A Computational Introduction to Number Theory and Algebra by Victor Shoup, Cambridge University Press. 978-0521516440
  4. A First Course in Probability, Sheldon Ross, Pearson Education, ISBN 978-9356064034.
  5. Sets, Logic and Categories, Peter J Cameron, Springer, ISBN 978-1852330569

References

  1. Discrete Mathematics: Elementary and Beyond by László Lovász, József Pelikán, Katalin Vesztergombi, Springer 2003, ISBN: 978-0387955858.
  2. Discrete Mathematics and Applications by Kenneth Rosen, 7th Edition, McGraw-Hill Education 2012, ISBN: 978-0073383095.
  3. Invitation to Discrete Mathematics by Jiří Matoušek and Jaroslav Nešetřil (2nd Edition) Oxford University Press, ISBN: 978-0198570424.
  4. Introduction to Probability for Computing, Mor Harchol-Balte, Cambridge University Press, ISBN 978-1009309073

Past Offerings

(Note: Past offerings could be under a different course number.)
  • 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 CS5021
Course Credits 3-1-0-4
Course Category PMT
Proposing Faculty Deepak Rajendraprasad and Jasine Babu
Approved on Senate of IIT Palakkad
Course prerequisites MA4999 OR CS4999
Course status NEW
Course revision information Revision of CS5013 Topics in Discrete Mathematics from MCaM 2020 curriculum.
Course pre-revision code CS5013