Maths for Computing: CSL2040

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

– Stephen Cook

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.

Evaluations

  1. 40% - Assignments.
  2. 30% - Two minors (15% each).
  3. 30% - Major.

Office Hours

Thursday: 3-5 PM

Lectures

  1. Course Overview, Administrivia, Logic, Propositions (Slides )
  2. Compound Propositions, Truth Table (Slides )
  3. Compound Propositions (contd.), Logical Equivalence (Slides )
  4. Logical Equivalence, Predicates and Quantifiers (Slides )
  5. Quantifiers (contd.), Well-formed Formulas, Logical Equivalence of WFFs (Slides )
  6. Rules of Inferences (Slides )
  7. Rules of Inferences (contd.), Introduction to Proofs (Slides )
  8. Introduction to Proofs (contd.), Direct Proofs, Proof by Contraposition (Slides )
  9. Proofs by Contraposition (contd.), Proof by Contradiction (Slides )
  10. Proofs by Contradiction (contd.), Proof by Exhaustion (Slides)
  11. Proof by Exhaustion (contd.), Existence Proof, Forward & Backward Reasoning (Slides)
  12. Mathematical Induction (Slides)
  13. More Examples on Mathematical Induction, Flawed Proofs (Slides)
  14. Strong Induction, Tips for Good Proofs (Slides)
  15. Basics of Sets & Functions (Slides)
  16. Infinite Sets & Countability (Slides)
  17. Countability (contd.) and Relations (Slides)
  18. Equivalence Relation and Partial Ordering (Slides)
  19. Pigeonhole Principle (Slides)
  20. Elementary Counting Problems (Slides)
  21. Elementary Counting Problems (contd.) (Slides)
  22. Binomial Theorem and Binomial Coefficients (Slides)
  23. Multinomial Theorem and Principle of Inclusion-Exclusion (Slides)
  24. Principle of Inclusion-Exclusion (contd.) and its applications (Slides)
  25. Balls and Boxes (Slides)
  26. Balls and Boxes (contd.) & Catalan Number (Slides)
  27. Introduction to Graph Theory (Slides)
  28. Euler Tours, More Notations (Slides)
  29. Hamiltonian Cycles, Isomorphic Graphs (Slides)
  30. Trees (Slides)
  31. Colouring, Bipartite Graphs (Slides)
  32. Matching (Slides)
  33. Matching (contd.), Hall’s Marriage Theorem (Slides)
  34. Planar Graphs (Slides)
  35. Planar Graphs (contd.) (Slides)
  36. Introduction to Theory of Computation, Languages, DFA (Slides)
  37. More DFAs, Pumping Lemma (Slides)
  38. Context-free Grammars and Languages (Slides)
  39. Turing Machines (Slides)
  40. TM Example, Encoding of a TM (Slides)
  41. Encodings (contd.), Computers vs Turing machine, Halting Problem (Slides)
  42. Complement of HALT, More Undecidable Languages (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
  14. Tutorial 14

Assignments

  1. Assignment 1 ( Solutions)
  2. Assignment 2 ( Solutions)
  3. Assignment 3 ( Solutions)
  4. Assignment 4 ( Solutions)
  5. Assignment 5 ( Solutions)
  6. Assignment 6 ( Solutions)