COMP 2711H - Honors Discrete Mathematics
Fall Semester 2024-25
Number of Students: 82
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