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
- Discrete mathematics and its applications by Kenneth H. Rosen.
- A Walk Through Combinatorics by Miklós Bóna.
Evaluations
- 40% - Assignments.
- 30% - Two minors (15% each).
- 30% - Major.
Office Hours
Thursday: 3-5 PMLectures
- Course Overview, Administrivia, Logic, Propositions (Slides )
- Compound Propositions, Truth Table (Slides )
- Compound Propositions (contd.), Logical Equivalence (Slides )
- Logical Equivalence, Predicates and Quantifiers (Slides )
- Quantifiers (contd.), Well-formed Formulas, Logical Equivalence of WFFs (Slides )
- Rules of Inferences (Slides )
- Rules of Inferences (contd.), Introduction to Proofs (Slides )
- Introduction to Proofs (contd.), Direct Proofs, Proof by Contraposition (Slides )
- Proofs by Contraposition (contd.), Proof by Contradiction (Slides )
- Proofs by Contradiction (contd.), Proof by Exhaustion (Slides)
- Proof by Exhaustion (contd.), Existence Proof, Forward & Backward Reasoning (Slides)
- Mathematical Induction (Slides)
- More Examples on Mathematical Induction, Flawed Proofs (Slides)
- Strong Induction, Tips for Good Proofs (Slides)
- Basics of Sets & Functions (Slides)
- Infinite Sets & Countability (Slides)
- Countability (contd.) and Relations (Slides)
- Equivalence Relation and Partial Ordering (Slides)
- Pigeonhole Principle (Slides)
- Elementary Counting Problems (Slides)
- Elementary Counting Problems (contd.) (Slides)
- Binomial Theorem and Binomial Coefficients (Slides)
- Multinomial Theorem and Principle of Inclusion-Exclusion (Slides)
- Principle of Inclusion-Exclusion (contd.) and its applications (Slides)
- Balls and Boxes (Slides)
- Balls and Boxes (contd.) & Catalan Number (Slides)
- Introduction to Graph Theory (Slides)
- Euler Tours, More Notations (Slides)
- Hamiltonian Cycles, Isomorphic Graphs (Slides)
- Trees (Slides)
- Colouring, Bipartite Graphs (Slides)
- Matching (Slides)
- Matching (contd.), Hall’s Marriage Theorem (Slides)
- Planar Graphs (Slides)
- Planar Graphs (contd.) (Slides)
- Introduction to Theory of Computation, Languages, DFA (Slides)
- More DFAs, Pumping Lemma (Slides)
- Context-free Grammars and Languages (Slides)
- Turing Machines (Slides)
- TM Example, Encoding of a TM (Slides)
- Encodings (contd.), Computers vs Turing machine, Halting Problem (Slides)
- Complement of HALT, More Undecidable Languages (Slides)
Tutorials
- Tutorial 1
- Tutorial 2
- Tutorial 3
- Tutorial 4
- Tutorial 5
- Tutorial 6
- Tutorial 7
- Tutorial 8
- Tutorial 9
- Tutorial 10
- Tutorial 11
- Tutorial 12
- Tutorial 13
- Tutorial 14