COMP 2711H - Honors Discrete Mathematics
Fall Semester 2024-25
Number of Students: 84
Average Rating by the Students: 4.58/5.0
Syllabus
Instructor: Amir Goharshady (goharshady@cse.ust.hk, amir.goharshady.com)
Office Hours: Use this link [the link is only available to HKUST students on canvas] to schedule office hours directly on my calendar. You can book up to two weeks in advance. Feel free to book several consecutive sessions if you need more time. You can also show up as a group if you like.
My office is CYT 3006 (3rd floor, the lift next to Subway).
Feel free to email me at any time. I answer as soon as possible and usually within hours. Email me if you have a question, want to schedule a meeting on zoom, need advice for the course or your studies in general, are interested in learning Persian/German, want to do an MPhil/PhD, or whatever comes to your mind. I don't bite :-)
TAs: Xuran Cai (xcaiay@connect.ust.hk) and Zhaorun Lin (zlinba@connect.ust.hk)
Feel free to email the TAs at any time with questions or if you would like to schedule a meeting with them. They would be happy to help you.
Summary: This course is an advanced (honors) version of "COMP 2711: Discrete Mathematical Tools for Computer Science" which provides a much more in-depth treatment of a wide variety of important mathematical concepts that form the theoretical basis of modern computer science.
The course will cover the following material:
Proofs and Reasoning: Propositional Logic, First-order (Predicate) Logic, Quantifiers, Proof by contradiction, Mathematical Induction, the Pigeonhole Principle, the Invariant Principle, the Extremal Principle, ...
Set Theory: ZMC, Peano's Axioms, Dedekind Cuts, Relations, Functions, Ordinals and Cardinals, Russel's Paradox, ...
Enumerative Combinatorics: Rules of Sum and Product, Permutations and Combinations, Inclusion-Exclusion, Catalan and Stirling Numbers, Generating Functions, Recurrence Relations, Double Counting, ...
Probability Theory: Discrete and Countable Probability Spaces, Axiomatic Probability Theory, Measure Functions, Lebesgue Integrals, Conditional Probability, Independence, Random Variables, Bayesian Reasoning, Expectation, Stochastic Processes, Markov Chains, Markov Decision Processes, ...
Number Theory: Divisibility, GCD, LCM, Primes, Congruence, Chinese Remainder Theorem, Theorems of Fermat, Euler and Wilson, Quadratic Reciprocity Law, the RSA and El-Gamal Cryptosystems, ...
Graph Theory: Adjacency, Walks, Paths, Cycles, (Strong) Connectivity, Distance, Trees, Spanning Trees, Bipartite Graphs, Matchings, Shortest Paths, ...
Game Theory: Combinatorial Games, Sprague-Grundy Theorem, Normal Form (Nash) Games, Nash Equilibria, Correlated Equilibria, Infinite Games on Graphs, ...
Recommended Books:
During the course, you will be assigned reading and watching material from books (available at the HKUST library) and youtube. Much of this material comes from the following books, but we will not cover any of these books completely. Interested students are strongly encouraged to read them on their own. These are all excellent and highly enjoyable reads!
Discrete and Combinatorial Mathematics by Grimaldi
Concrete Mathematics by Knuth et al
Principles and Techniques in Combinatorics by Chen and Koh
A First Course in Probability by Ross
Elementary Number Theory by Burton
Set Theory: A First Course by Cunningham
Introduction to Graph Theory by West
Algorithmic Game Theory by Nisan and Roughgarden
Problem Solving Strategies by Engel
102 Combinatorial Problems by Andreescu and Feng
Winning Ways for Your Mathematical Plays by Berlekamp et al
Grading:
Homeworks: 4 x 10%
Each homework has a deadline and you must submit your solutions before this deadline. The TAs and I will read your solutions and give you detailed feedback. You are then allowed to resubmit the homework. Your score will be the maximum of your two attempts. We reserve the right to disallow resubmissions if your initial submission is of low quality or shows a lack of effort.
Midterm Exam: 30%
Time: Friday, October 18, 2024, 18:00-22:00
Place: LTC
Final Exam: 30%
covers the entire course, not just the second half.
This is a challenging course and most students will achieve homework/exam marks that are lower than what they are used to in other courses. You do not need 90% to get an A in this course. Anyone who shows mastery of all the topics will be awarded an A or A+.
LaTeX Requirement: All written assignments must be submitted as standard pdf files generated by LaTeX. We do NOT accept any other formats. Handwritten files or those generated by other typesetting software will be rejected without grading. If you are not familiar with LaTeX, https://www.overleaf.com/ is a great resource. If your solutions include figures, you should draw them using either tikz, https://app.diagrams.net/, or a similar tool and embed them in LaTeX.
Attendance Policy: There is no distinction between lectures and tutorials in this course. You are required to attend all of them according to UST policy. Attendance does not contribute to the grade.
Plagiarism Policy: You may use any external source, including search and generative AI, in all assignments in this course. However, you must not collaborate with another student. We have zero tolerance for plagiarism and the minimum penalty is a grade of F.
Recordings: All sessions will be recorded and made available on canvas.
Lecture Notes: The TAs will prepare lecture notes for each session. These will also be uploaded on canvas. Preparing these notes can take a few days. Be patient and nice to the TAs!
Problem Sets: We release problem sets every week. These are problems that you must solve on your own to improve your understanding of the topics in this course. We do not grade them, but they are mandatory. Do not skip them. The same point applies to exercises in the reading material. One can learn math only by picking up pen and paper and solving problems. They are also the best possible practice for the exams. If you cannot solve a problem even after giving it significant time and effort, feel free to schedule an office hour with me or the TAs.
Lecture 1: Proposotional Logic (2 September 2024)
Reading: Chapter 2 of Grimaldi (Fundamentals of Logic)
Lecture 2: Predicate Logic and Peano's Axioms (2 September 2024)
Reading: Chapter 2 of Grimaldi (Fundamentals of Logic)
Lecture 3: Induction, Well-ordering and Infinite Descent (4 September 2024)
Lecture 4: Induction Problems and Strong Induction (9 September 2024)
Video: Proof by Strong Induction
Pause the videos whenever a problem is posed and try to solve it on your own first, before watching the solution.
Reading: Chatpers 3 and 8 of Engel (The Extremal Principle, The Induction Principle)
It is really important that you give every problem an honest and serious attempt before reading its solution. You must reach mastery in using mathematical induction and its equivalent forms. All of the future modules in this course depend on such mastery.
Lecture 5: Solving More Induction Problems (9 September 2024)
Reading: Chatpers 3 and 8 of Engel (The Extremal Principle, The Induction Principle)
Lecture 6: Counting, Permutations, Combinations, Balls and Walls (11 September 2024)
Reading: Chapter 1 of Grimaldi (Fundamental Principles of Counting)
Reading: Chapter 1 of Chen and Koh (Permutations and Combinations) -- Very Important
Reading: Chapter 1 of Ross (Combinatorial Analysis)
It is crucial that you solve every exercise at the end of these chapters.
Fun to Read: Which Rectangular Chessboards Have a Knight's Tour?
Lecture 7: Solving Counting Problems (16 September 2024)
Reading: Chapter 1 of Chen and Koh (Permutations and Combinations) -- Very Important
Solve the first 24 Problems of Andreescu and Feng
Lecture 8: More Counting (16 September 2024)
Solve Problems 25 to 51 of Andreescu and Feng
Homework 1
TA Session 1 (20 September 2024)
Lecture 9: Principle of Inclusion and Exclusion (23 September 2024)
Reading: Chaptes 2 and 4 of Chen and Koh (Binomial Coefficients, Inclusion-Exclusion)
Lecture 10: Generalized Principle of Inclusion and Exclusion (23 September 2023)
Reading: Chaptes 2 and 4 of Chen and Koh (Binomial Coefficients, Inclusion-Exclusion)
Reading: Chapter 8 of Grimaldi (Inclusion-Exclusion)
Lecture 11: Pigeonhole Principle (25 September 2024)
Reading: Chapter 3 of Chen and Koh (Pigeonhole and Ramsey)
Reading: Chapter 4 of Engel (Box Principle)
Solve Advanced Problems 1 to 15 of Andreescu and Feng
TA Session 2 (27 September 2024)
Lecture 12: Graphs, Trees, Paths and Walks (30 September 2024)
Reading: Sections 1.1 and 1.2 of West (What is a Graph?, Paths, Cycles and Trails)
Most of the theorems we proved in class were from these sections, but the proofs are often different. So, you should read the book and also solve the exercises.
Lecture 13: More Theorems on Graphs and Trees (30 September 2024)
Reading: Sections 1.3 and 1.4 of West (Vertex Degrees & Counting, Directed Graphs)
When reading this text, read each theorem but try to prove it yourself first before reading the proof. Also, make sure you solve all the exercises.
Solve Advanced Problems 16 to 30 of Andreescu and Feng
Lecture 14: Even More Theorems on Graphs and Trees (2 October 2024)
Reading: Sections 2.1 and 2.2 of West (Trees and Distance: Basic Properties, Spanning Trees)
Reading: Chapters 11 and 12 of Grimaldi (Graph Theory, Trees)
TA Session 3 (4 October 2024)
Lecture 15: Minimum Spanning Trees, Directed Graphs, DAGs (7 October 2024)
Before watching the next video, try to prove that Prim's algorithm is correct. Can you find a proof similar to the one we saw for Kruskal?
Reading: Chapters 1 and 2 of West (Fundamental Concepts, Trees and Distance)
You should read everything in these two chapters, including parts that are marked as "optional" in the book and solve all exercises.
Solve Advanced Problems 31 to 40 of Andreescu and Feng
Lecture 16: Tree-based Algorithms and Huffman Coding (7 October 2024)
Reading: Section 2.3 of West (Optimization and Trees)
Lecture 17: Distance, Shortest Paths and Matchings (9 October 2024)
Homework 2
TA Session 4 (11 October 2024)
Lecture 18: Matchings, Vertex Covers, Edge Covers and Independent Sets (14 October 2024)
Reading: Section 3.1 of West (Matchings and Covers)
Lecture 19: Network Flow and the Ford-Fulkerson Algorithm (14 October 2024)
Lecture 20: Stable Matchings and Graph Coloring (16 October 2024)
Reading: Subsection 3.2.3 of West (Stable Matchings)
Reading: Section 5.1 of West (Vertex Colorings and Upper Bounds) -- Brooks' Theorem is not part of the syllabus
Lecture 21: Divisibility and Greatest Common Divisor (21 October 2024)
Reading: Chapters 1 and 2 of Burton (Preliminaries, Divisibility Theory)
Playlist: Introduction to Number Theory (Watch Lectures 3 and 4)
Lecture 22: Prime Factorizations and the Fundamental Theorem of Arithmetic (21 October 2024)
Reading: Sections 2.4 to 3.3 of Burton (Euclid to Goldbach)
Lecture 23: Congruence, Modular Multiplicative Inverse and the Chinese Remainder Theorem (23 October 2024)
Reading: Chapter 4 of Burton (Congruences)
It is really important that you read the book since it provides different proofs than the ones covered in the lecture.
Video Playlist: Chinese Remainder Theorem
Make sure you watch all of this playlist, especially the last video.
Solve Problems 14, 20, 27, 47, 50, 69, 77, 112, 122 and 451 of ProjectEuler.net
TA Session 5 (25 October 2024)
Lecture 24: Fermat's Little Theorem, Euler's Theorem, Wilson's theorem (28 October 2024)
Playlist: Introduction to Number Theory (Watch Lectures 5 to 14, Primes to Euler's Totient)
Reading: Chapters 5 and 7 of Burton (Fermat's Theorem, Euler's Generalization of Fermat's Theorem)
Lecture 25: Diffie-Hellman-Merkle Key Exchange and ElGamal Encryption (28 October 2024)
Recommended Reading: Chapter 10 of Burton (Intro to Crypto)
Lecture 26: RSA Encryption and Digital Signatures (30 October 2024)
TA Session 6 (1 November 2024)
Lecture 27: Russell's Paradox and Zermelo–Fraenkel Axioms (4 November 2024)
Lecture 28: Axiom of Infinity and Bijections (4 November 2024)
Lecture 29: Countability and the Theorems of Cantor, Tarski and Schröder–Bernstein
TA Session 7 (8 November 2024)
Homework 3
Lecture 30: The Set of Real Numbers (11 November 2024)
Lecture 31: |ℝ|=|P(ℕ)| and the Axiom of Choice (11 November 2024)
Lecture 32: Introduction to Probability Theory (13 November 2024)
Reading: Chapter 2 of Ross (Axioms of Probability), including sections marked by *
TA Session 8 (15 November 2024)
Lecture 33: Conditional Probability, Independence and Expectation (18 November 2024)
Watch: Philosophers are not smart enough for probability theory!
Reading: Chapters 3 and 4 of Ross (Conditional Probability, Independence, Random Variables)
Note: We did not cover variance and common probability distributions in the lectures (due to being too easy), but they are part of the syllabus. So, make sure you read everything in these chapters.
Lecture 34: Solving Problems using Linearity of Expectation (18 November 2024)
Homework 4
Lecture 36: Nim and the Sprague-Grundy Theorem (25 November 2024)
Lecture 37: One-shot Games and Nash Equilibria (25 November 2024)
Reading: Chapter 1 of the Algorithmic Game Theory Book (Basic Solution Concepts)
Lecture 38: Two-player Infinite-duration Games on Graphs (27 November 2024)
Playlist: COMP 6613B's Lectures on Graph Games (Watch Lectures 6 and 7, Lecture 8 is Optional
Recommended Playlist: Linear-time Temporal Logic
LTL is not part of the syllabus. It's just a recommendation for you to see what the deal with ♢s and □s was.