Maths for Computing: CSL2040

"The landscape of computer science is surveyed by the theorems of mathematics, while algorithms blaze the trails of possibility."

– Unknown

Course Description

Welcome to the Maths for Computing course!

This course is designed to provide computer science and engineering students with a strong foundation in elementary discrete mathematics. It focuses on (i) introducing new mathematical objects that are useful in computer science and (ii) proof writing, while recognizing and addressing fallacious reasoning and statements. The key areas that the course covers are logic, proof methods, set theory, counting techniques, graph theory, and models of computation.

Course Information

Prerequisites

None.

Books

  1. Discrete mathematics and its applications by Kenneth H. Rosen.
  2. A Walk Through Combinatorics by Miklós Bóna.

Evaluation Scheme

  1. 30% - Quiz (Best 3 of 4).
  2. 30% - Minor.
  3. 40% - Major.

Office Hours

Mail me to fix an appointment

Lectures

  1. Course overview, Administrative Details, Logic ( Slides )
  2. Propositions, Compound Propositions, Truth Table ( Slides )
  3. Compound Propositions, Logical Equivalence, Predicates ( Slides )
  4. Predicates, Quantifiers, Well-formed Formulas ( Slides )
  5. Quantifiers (contd.), Rules of Inferences ( Slides )
  6. Rules of Inferences (contd.), Introduction to Proofs ( Slides )
  7. Direct Proofs, Proof by Contraposition ( Slides )
  8. Proof by Contradiction, Proof By Exhaustion ( Slides )
  9. Proof by Exhaustion (contd.), Existence Proof, Forward & Backward Reasoning ( Slides )
  10. Mathematical Induction ( Slides )
  11. More Examples on Mathematical Induction, Flawed Proofs ( Slides )
  12. Strong Induction, Tips for Proof Writing ( Slides )
  13. Infinite Sets and Countability ( Slides ) ( Basics of Set Theory )
  14. Uncountable Sets and Relations ( Slides )
  15. Equivalence Relation and Partial Ordering ( Slides )
  16. Pigeonhole Principle ( Slides )
  17. Elementary Counting Problems ( Slides )
  18. Elementary Counting Problems (contd.) ( Slides )
  19. Binomial Theorem and Binomial Coefficients ( Slides )
  20. Multinomial Theorem and Principle of Inclusion-Exclusion ( Slides )
  21. Applications of PIE, Balls and Boxes ( Slides )
  22. Balls and Boxes (Contd.) ( Slides )
  23. Catalan Number and Introduction to Graph Theory ( Slides )
  24. Handshaking Lemma, Euler Tours ( Slides )
  25. More Notations, Hamiltonian Cycles ( Slides )
  26. Graph Isomorphism, Trees ( Slides )
  27. Trees(contd.), Colouring, Bipartite Graphs ( Slides )
  28. Matching ( Slides )
  29. Matching (contd.), Hall’s Marriage Theorem ( Slides )
  30. Hall’s Marriage Theorem (contd.), Planar Graphs ( Slides )
  31. Non-planarity of K_{3,3} and K_5  ( Slides )
  32. 6-colour Theorem, 5-colour Theorem, Intro. to Theory of Computation ( Slides )
  33. Deterministic Finite Automata ( Slides )
  34. More DFAs, Pumping Lemma ( Slides )
  35. Pumping Lemma (contd.), Context Free Grammars ( Slides )
  36. Context Free Grammars (contd.), Turing machines ( Slides )
  37. Turing machines (contd.) ( Slides )
  38. Computers vs TMs, Encoding of a TM, Universal TM ( Slides )
  39. Halting Problem and its Complement ( Slides )
  40. Reductions and more Undecidable Problem ( Slides )

Tutorials

  1. Tutorial 1
  2. Tutorial 2
  3. Tutorial 3
  4. Tutorial 4
  5. Tutorial 5
  6. Tutorial 6
  7. Tutorial 7
  8. Tutorial 8
  9. Tutorial 9
  10. Tutorial 10
  11. Tutorial 11
  12. Tutorial 12
  13. Tutorial 13