This is a revision of the course CS2020

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