- Instructor: Anthony Man-Cho So (manchoso at se.cuhk.edu.hk)
- Office Hours: By appointment and online until further notice
- Lecture Time/Location:
- Mondays 10:30am - 12:15pm, online via ZOOM
- Wednesdays 1:30pm - 2:15pm, online via ZOOM
- Thursdays 10:30am - 12:15pm, online via ZOOM
- Teaching Assistants:
- Jiajin Li (jjli at se.cuhk.edu.hk)
- Office Hours: By appointment and online until further notice
- Xiaolu Wang (xlwang at se.cuhk.edu.hk)
- Office Hours: By appointment and online until further notice
- Online Q&A Forum: Follow this link.
Course Description
Just as calculus is the mathematical foundation for natural sciences, discrete mathematics is the mathematical foundation for computing sciences. In this course, we will cover the basic techniques of discrete mathematics, which are essential for manipulating and reasoning about finite or countable sets of objects. Applications from various disciplines, such as computer science, operations research, and probability, will be used to illustrate the theory.
Course Requirements
- Homework Sets (35%)
- Midterm Examination (20%)
- Final Examination (20%)
- Essay (25%)
Primary Text
The primary text for this course is Eric Lehman, F. Thomson Leighton, Albert R. Meyer (LLM), Mathematics for Computer Science, 2018.
General References
- Richard A. Brualdi, Introductory Combinatorics (5th Edition), Pearson Education, Inc., 2010.
- Susanna S. Epp , Discrete Mathematics with Applications (4th Edition), Brooks/Cole Cengage Learning, 2011.
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik (GKP), Concrete Mathematics (2nd Edition), Addison-Wesley, 1994.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications (7th Edition), McGraw-Hill, 2012.
Schedule and Reading
- Week 1: Sep 7 Information Sheet, Notes. Familiarize yourselves with the material in LLM Chapters 1 to 3. Sep 9 Notes. Sep 10 Notes. Read LLM Chapter 5.
- Week 2: Sep 14 Notes. Read LLM Chapters 14.1-14.2. Sep 16 Notes. Sep 17 Notes. Read LLM Chapter 14.6. Suggested Reading: GKP Chapters 2.3-2.4.
- Week 3: Sep 21 Notes. Suggested reading: GKP Chapters 3.1, 3.2. Sep 23 Notes. Suggested reading: Repertoire method. Sep 24 Notes. Suggested reading: GKP Chapter 1.3.
- Week 4: Sep 28 Notes. Read LLM Chapter 16.1. Sep 30 Notes. Read LLM Chapters 16.3-16.4. Suggested reading: GKP Chapters 7.2 and 7.3 (Examples 1 and 2). Oct 1 No class (National Day Holiday)
About the Essay
Towards the end of the course, you will need to write a short (4-5 pages), complete account of a result in discrete mathematics. The essay should include the background, statement, proof, and applications of the result. More details will be announced later in the course.
Homework Sets