- Instructor: Anthony Man-Cho So (manchoso at se.cuhk.edu.hk)
- Office Hours: By appointment, in ERB 604 or online
- Lecture Time/Location:
- Mondays 10:30am - 12:15pm, in SC L3
- Wednesdays 1:30pm - 2:15pm, in ERB 803
- Thursdays 10:30am - 12:15pm, in MMW 710
- Teaching Assistants:
- Xiaolu Wang (xlwang at se.cuhk.edu.hk)
- Taoli Zheng (tlzheng at se.cuhk.edu.hk)
- Office Hours: Tuesdays 2:00pm - 3:30pm, in ERB 905 or online
- 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, 2015.
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 6 Information Sheet, Notes. Familiarize yourselves with the material in LLM Chapters 1 and 3. Sep 8 Notes. Read LLM Chapter 5.1. Sep 9 Notes. Read LLM Chapters 5.2-5.3.
- Week 2: Sep 13 Notes. Read LLM Chapters 13.1-13.2. Sep 15 Notes. Sep 16 Notes. Read LLM Chapter 13.6. Suggested reading: GKP Chapters 2.3-2.4.
- Week 3: Sep 20 Notes. Suggested reading: GKP Chapters 3.1, 3.2. Sep 22 No class (Day following the Chinese Mid-Autumn Festival) Sep 23 Notes. Suggested reading: Repertoire method.
- Week 4: Sep 27 Notes. Read LLM Chapter 15.1. Suggested reading: GKP Chapter 1.3. Sep 29 Notes. Read LLM Chapters 15.3, 15.4.1. Sep 30 Notes. Read LLM Chapters 15.4.2, 13.7.2. Suggested reading: GKP Chapters 7.2 and 7.3 (Examples 1 and 2).
- Week 5: Oct 4 Notes. Read LLM Chapter 13.7. Oct 6 Notes. Oct 7 Notes. Read LLM Chapters 21.4.1-21.4.3. Optional reading: LLM Chapter 21.4.4. Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009. Chapter 9.3 (Selection in worst-case linear time). This describes the algorithm for selection and derives the recurrence discussed in class.
- Week 6: Oct 11 Notes. Suggested reading: Apostol: An Elementary View of Euler's Summation Formula. The American Mathematical Monthly 106(5): 409-418, 1999. Oct 13 Class suspended due to typhoon. Oct 14 No class (Day following the Chung Yeung Festival).
- Week 7: Oct 18 Notes. Read LLM Chapter 4.1. Oct 20 Notes. Read LLM Chapters 14.1-14.2. Oct 21 Notes. Read LLM Chapters 14.3-14.5.
- Week 8: Oct 25 Notes. Read LLM Chapter 14.10. Oct 27 Midterm Review. Notes. Oct 28 Midterm Examination.
- Week 9: Nov 1 Notes. Read LLM Chapters 14.5-14.6. Suggested reading: LLM Chapters 14.7-14.8. Nov 3 Notes. Read LLM Chapter 14.9. Nov 4 Congregation.
- Week 10: Nov 8 Notes. Read LLM Chapters 16.2, 16.5.1-16.5.3. Nov 10 Notes. Read LLM Chapters 16.1, 16.4. Nov 11 Notes.
- Week 11: Nov 15 Notes. Suggested reading: GKP Chapters 5.1, 7.4. Nov 17 Notes. Nov 18 Notes. Read LLM Chapters 11.1-11.2. Suggested reading: GKP Chapter 7.5 (Examples 1-4).
- Week 12: Nov 22 Notes. Read LLM Chapters 11.8, 11.9.1, 11.10.1-11.10.2. Nov 24 Notes. Read LLM Chapters 11.8, 11.9.1, 11.9.4, 11.10.2. Nov 25 Notes. Read LLM Chapter 11.3.
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 (Assignment Box: C10, ERB 5/F)