Syllabus:

Logic and set theory. Introduction to proofs, axiomatic method, proof patterns. Well ordering principle. Logical formulas - propositional and predicate. Sets, relations, equivalences and partial orders. Induction. Recursive definitions. Infinite Sets: Cantor’s theorem, diagonalization argument, halting problem. Logic of sets. [12 lectures + 4 tutorial sessions ]

Graph Theory. Graphs, degree. Common graphs. Walks, paths, connectivity, cycles, trees, forests. Cliques, Independent sets. Graph Isomorphism, bipartite graphs and matchings. Colouring. Planar graphs: Euler’s formula, 6-colouring of planar graphs. Regular polyhedra. [8 lectures + 3 tutorial sessions]

Combinatorics. Product rule, division rule, counting subsets, sequences with repetitions - binomial and multinomial theorems. Pigeonhole principle. Inclusion-exclusion. Combinatorial proofs. Twelvefold way. Recurrence relations - Fibonacci numbers and Towers of Hanoi puzzle. [8 lectures + 3 tutorial sessions]

Discrete Probability. Events and probability spaces, The four step method, birthday principle. Set theory and probability. Conditional probability, law of total probability. Independence. Probability versus confidence. Random variables: independence. distribution functions, expectations. Linearity of Expectation [14 lectures + 4 tutorial sessions]

Learning Outcomes

  1. Use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions, and integers.

  2. Evaluate elementary mathematical arguments and identify fallacious reasoning (not just fallacious conclusions).

  3. Synthesize new proofs based on standard proof patterns.

  4. Apply graph-theoretic models to solve problems like job allocation, scheduling, connectivity etc.

  5. Calculate numbers of possible outcomes of elementary combinatorial processes such as permutations and combinations.

  6. Calculate probabilities and discrete distributions for simple combinatorial processes; calculate expectations.

Textbook

  1. Mathematics for Computer Science. Eric Lehman, F Thomson Leighton, Albert R Meyer. This book is available online under the terms of the Creative Commons Attribution ShareAlike 3.0 license. URL: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Printed version: 12th Media Services. ISBN-13: 978-1680921229.

Reference

  1. Discrete Mathematics and Applications. Kenneth Rosen (7th Edition, 2012), McGraw-Hill Education (ISBN-13: 978-0073383095)

  2. Invitation to Discrete Mathematics. Jiří Matoušek and Jaroslav Nešetřil (2nd Edition) Oxford University Press (ISBN-13: 978-0198570424)

  3. Discrete Mathematics: Elementary and Beyond. László Lovász, József Pelikán, Katalin Vesztergombi, Springer 2003, ISBN-13: 978-0387955858.

Popular Readings

  1. Logicomix: An epic search for truth. Apostolos Doxiadis and Christos Papadimitriou. Bloomsbury USA. ISBN-13: 978-1596914520

  2. What is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles. Raymond M. Smullyan. Dover Publications.

    ISBN-13: 978-0486481982

  3. Proofs from THE BOOK. Martin Aigner and Günter M. Ziegler. Springer. ISBN-13 : 978-3642008559

  4. Combinatorics: A Very Short Introduction. Robin Wilson. Oxford University Press. ISBN-13: 978-0198723493

Notes

  1. This course is modelled along the Mathematics for Computer Science course (6.042J, Spring 2015) at MIT.

Past Offerings

(Note: Past offerings could be under a different course number.)
  • Offered in Aug-Nov, 2023 by Deepak Rajendraprasad
  • Offered in Jan-May, 2023 by Jasine Babu
  • Offered in Jan-May, 2022 by Satyadev Nandakumar
  • Offered in Jan-May, 2021 by Deepak, Krithika
  • Offered in Jan-May, 2020 by Jasine
  • Offered in Jan-May, 2019 by Deepak

Course Metadata

Item Details
Course Title Discrete Mathematics
Course Code CS2020A
Course Credits 3-1-0-4
Course Category PMC
Proposing Faculty Krishnamoorthy Dinesh & Deepak Rajendraprasad
Approved on Senate 20 of IIT Palakkad
Course status NEW
Course revision information Revision of CS2020 Discrete Mathematics for Computer Science & CS2010 Logic for Computing
Course pre-revision code CS2020