ESTR 2004: Discrete Mathematics for Engineers (ELITE Stream)
2021-22 First Term
Announcements
- NEW: The final examination will mostly cover the material after the midterm examination; i.e., from Week 7 (starting with the lecture on October 20, 2021) to Week 13 (up to and including the lecture on December 2, 2021). However, you are expected to be familiar with some of the techniques covered in the midterm examination. You are allowed to bring one A4-sized cheat sheet. You can write or print on both sides of the cheat sheet. No calculator or other material will be allowed. Please contact the teaching staff if you need any clarification on the rules.
- NEW: Here is the solution to Homework 6.
- NEW: Here are some additional practice problems.
- Here is the midterm solution.
- Welcome to ESTR 2004! This is the ELITE Stream version of ENGG 2440. The coverage of topics will be slightly different from that in ENGG 2440. In particular, we will not cover LLM Chapters 1 and 3. Students should read up these chapters on their own.
- The Thursday tutorials will be used as lectures. For the tentative class schedule, please see Section 5 of the Information Sheet.
- To better facilitate discussions and Q&As, we have set up an online platform. Please follow this link to sign up.
General Information
- 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.
- Week 13: Nov 29 Notes. Dec 1 Notes. Dec 2 Notes. Read LLM Chapter 11.5.
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)
Last Updated: December 8, 2021