## 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