COMP 2711H Reading

  1. Lecture 1: Propositional Logic
  2. Lecture 2: Predicate Logic and Peano's Axioms
  3. Lecture 3: Induction, Well-ordering and Infinite Descent
  4. Lecture 4: Induction Problems and Strong Induction
  5. Lecture 5: Solving More Induction Problems
  6. Lecture 6: Counting, Permutations, Combinations, Balls and Walls
  7. Lecture 7: Solving Counting Problems
    • Lecture Video
    • Reading: Chapter 1 of Chen and Koh (Permutations and Combinations) -- Very Important
  8. Lecture 8: More Counting
  9. TA Session 1
  10. Lecture 9: Principle of Inclusion and Exclusion
  11. Lecture 10: Generalized Principle of Inclusion and Exclusion (23 September 2023)
  12. Lecture 11: Pigeonhole Principle
  13. TA Session 2
  14. Lecture 12: Graphs, Trees, Paths and Walks
  15. Lecture 13: More Theorems on Graphs and Trees
  16. Lecture 14: Even More Theorems on Graphs and Trees
  17. TA Session 3
  18. Lecture 15: Minimum Spanning Trees, Directed Graphs, DAGs
  19. Lecture 16: Tree-based Algorithms and Huffman Coding
  20. Lecture 17: Distance, Shortest Paths and Matchings
  21. TA Session 4
  22. Lecture 18: Matchings, Vertex Covers, Edge Covers and Independent Sets
    • Lecture Video
    • Reading: Section 3.1 of West (Matchings and Covers)
  23. Lecture 19: Network Flow and the Ford-Fulkerson Algorithm
  24. Lecture 20: Stable Matchings and Graph Coloring
  25. Midterm Exam
  26. Lecture 21: Divisibility and Greatest Common Divisor
  27. Lecture 22: Prime Factorizations and the Fundamental Theorem of Arithmetic
  28. Lecture 23: Congruence, Modular Multiplicative Inverse and the Chinese Remainder Theorem
  29. TA Session 5
  30. Lecture 24: Fermat's Little Theorem, Euler's Theorem, Wilson's theorem
  31. Lecture 25: Diffie-Hellman-Merkle Key Exchange and ElGamal Encryption
  32. Lecture 26: RSA Encryption and Digital Signatures
  33. TA Session 6
  34. Lecture 27: Russell's Paradox and Zermelo–Fraenkel Axioms
  35. Lecture 28: Axiom of Infinity and Bijections
  36. Lecture 29: Countability and the Theorems of Cantor, Tarski and Schröder–Bernstein
  37. TA Session 7
  38. Lecture 30: The Set of Real Numbers
  39. Lecture 31: |ℝ|=|P(ℕ)| and the Axiom of Choice
  40. Lecture 32: Introduction to Probability Theory
    • Lecture Video
    • Reading: Chapter 2 of Ross (Axioms of Probability), including sections marked by *
  41. TA Session 8
  42. Lecture 33: Conditional Probability, Independence and Expectation
  43. Lecture 34: Solving Problems using Linearity of Expectation
  44. Lecture 35: Markov Chains
  45. Lecture 36: Nim and the Sprague-Grundy Theorem
  46. Lecture 37: One-shot Games and Nash Equilibria
  47. Lecture 38: Two-player Infinite-duration Games on Graphs
  48. TA Session 9
  49. TA Session 10
  50. TA Session 11