Course Information
Instructor: Purandar Bhaduri (Email:pbhaduri)
Department: Computer Science & Engineering
Semester: Monsoon, 2025-2026
Class Schedule: Wed, Thu, Fri (12:00 -- 12:55 AM)
Head Teaching Assistant: Siddharth Gaur (Email: sgaur)
Evaluation
- Mid-semester Exam: 40%
- End-semester Exam: 60%
Syllabus
The course will cover a selection of the following topics. Additional topics may also be touched upon.
- Introduction to Mathematical Proofs
- Basic Set Theory: Review of sets, functions, relations
- Logic: formulae, interpretations, methods of proof in propositional and predicate logic
- Number theory: division algorithm, Euclid's algorithm, fundamental theorem of arithmetic, Chinese remainder theorem
- Combinatorics: permutations, combinations, partitions, recurrences, generating functions
- Graph Theory: isomorphism, complete graphs, bipartite graphs, matchings, colourability, planarity
- Probability: conditional probability, random variables, probability distributions, tail inequalities
Textbooks
- Mathematics for Computer Science by Eric Lehman, F Thomson Leighton and Albert R Meyer, June 2018 edition. Class material from the MIT course based on the book.
- Basic Probability Theory by Robert B. Ash, Dover Books on Mathematics, 2008.
Other Sources
- Notes on Set Theory for Computer Science by Glynn Winskel at Cambridge University
- Course Lecture Notes by Stephen Cook, CSC 438F/2404F: Computability and Logic Fall, 2017 at University of Toronto. Refer to the notes on Propositional Calculus and Predicate Calculus.
Contact Information
For any questions regarding the course, use the MS Teams group for this class. You can also schedule an appointment in my office by email.