↢ Back to the List of Courses

COMP 2711H - Honors Discrete Mathematics

Fall Semester 2024-25

Number of Students: 84

Syllabus

Instructor: Amir Goharshady (goharshady@cse.ust.hk, amir.goharshady.com)

 

TAs: Xuran Cai (xcaiay@connect.ust.hk) and Zhaorun Lin (zlinba@connect.ust.hk)

 

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:

 

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!

 

Grading:

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)

Lecture 2: Predicate Logic and Peano's Axioms (2 September 2024)

Lecture 4: Induction Problems and Strong Induction (9 September 2024)

Lecture 5: Solving More Induction Problems (9 September 2024)

Lecture 6: Counting, Permutations, Combinations, Balls and Walls (11 September 2024)

Lecture 7: Solving Counting Problems (16 September 2024)

Lecture 8: More Counting (16 September 2024)

Homework 1

Lecture 9: Principle of Inclusion and Exclusion (23 September 2024)

Lecture 10: Generalized Principle of Inclusion and Exclusion (23 September 2023)

Lecture 11: Pigeonhole Principle (25 September 2024)

TA Session 2 (27 September 2024)

Lecture 12: Graphs, Trees, Paths and Walks (30 September 2024)

Lecture 13: More Theorems on Graphs and Trees (30 September 2024)

Lecture 14: Even More Theorems on Graphs and Trees (2 October 2024)

Lecture 15: Minimum Spanning Trees, Directed Graphs, DAGs (7 October 2024)

Homework 2

TA Session 4 (11 October 2024)

Lecture 18: Matchings, Vertex Covers, Edge Covers and Independent Sets (14 October 2024)

Lecture 20: Stable Matchings and Graph Coloring (16 October 2024)

Lecture 21: Divisibility and Greatest Common Divisor (21 October 2024)

Lecture 22: Prime Factorizations and the Fundamental Theorem of Arithmetic (21 October 2024)

Lecture 23: Congruence, Modular Multiplicative Inverse and the Chinese Remainder Theorem (23 October 2024)

TA Session 5 (25 October 2024)

Lecture 27: Russell's Paradox and Zermelo–Fraenkel Axioms (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 32: Introduction to Probability Theory (13 November 2024)

TA Session 8 (15 November 2024)

Lecture 33: Conditional Probability, Independence and 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)

Lecture 38: Two-player Infinite-duration Games on Graphs (27 November 2024)

TA Session 9 (27 November 2024)