COMP 2711H - Honors Discrete Mathematics
Fall Semester 2024-25
Number of Students: 84
Average Rating by the Students: 4.58/5.0
Fall Semester 2024-25
Number of Students: 84
Average Rating by the Students: 4.58/5.0
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.
Reading: Chapter 2 of Grimaldi (Fundamentals of Logic)
Reading: Chapter 2 of Grimaldi (Fundamentals of Logic)
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.
Reading: Chatpers 3 and 8 of Engel (The Extremal Principle, The Induction Principle)
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?
Reading: Chapter 1 of Chen and Koh (Permutations and Combinations) -- Very Important
Solve the first 24 Problems of Andreescu and Feng
Solve Problems 25 to 51 of Andreescu and Feng
Reading: Chaptes 2 and 4 of Chen and Koh (Binomial Coefficients, Inclusion-Exclusion)
Reading: Chaptes 2 and 4 of Chen and Koh (Binomial Coefficients, Inclusion-Exclusion)
Reading: Chapter 8 of Grimaldi (Inclusion-Exclusion)
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
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.
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
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)
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
Reading: Section 2.3 of West (Optimization and Trees)
Reading: Section 3.1 of West (Matchings and Covers)
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
Reading: Chapters 1 and 2 of Burton (Preliminaries, Divisibility Theory)
Playlist: Introduction to Number Theory (Watch Lectures 3 and 4)
Reading: Sections 2.4 to 3.3 of Burton (Euclid to Goldbach)
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
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)
Recommended Reading: Chapter 10 of Burton (Intro to Crypto)
Reading: Chapter 2 of Ross (Axioms of Probability), including sections marked by *
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.
Reading: Chapter 1 of the Algorithmic Game Theory Book (Basic Solution Concepts)
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.