ESTR 2004: Discrete Mathematics for Engineers (ELITE Stream)
2020-21 First Term
Announcements
- NEW: Here is the final solution.
- Here is the solution to Homework 6.
- The final examination will be held in an online format on December 14, 2020, from 12:30pm to 2:15pm. Please enter the usual ZOOM session by 12:20pm. The examination will mainly cover material from Week 7 to Week 13 (inclusive), but you are expected to be familiar with the techniques covered in Week 1 to Week 6 (inclusive). The examination paper will be distributed through both the ZOOM chat box and Blackboard.
You are allowed to use online material during the examination. However, no communication, whether you are the initiator or receiver, of any kind is allowed. In particular, please find a quiet place where you will not be disturbed during the examination. If you have any questions during the examination, you can contact the teaching staff privately via the ZOOM chat box. During the examination, you will need to turn on a camera showing your computer screen, desk, hands, and yourself. The whole session will be recorded.
At the end of the examination, you will have 10 minutes to scan/take a picture of your answer script and submit a single file in pdf/doc/docx format via Blackboard. In case you have difficulty submitting through Blackboard, you should email your answer script to the course instructor (manchoso at se.cuhk.edu.hk) immediately. Also, please make sure you include all the pages when you make the submission. Late submission will not be entertained regardless of the reason.
Please contact the teaching staff if you need any clarification on the rules.
- Welcome to ESTR 2004! This is the ELITE Stream version of ENGG 2440A/B. The coverage of topics will be slightly different from that in ENGG 2440. In particular, we will not cover LLM Chapters 1-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.
- The ZOOM link has already been emailed to those who have registered in the course.
General Information
- 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).
- Week 5: Oct 5 Notes. Read LLM Chapter 14.7.2. Oct 7 Notes. Read LLM Chapters 14.7.1-14.7.3, 14.7.5. Oct 8 Notes. Read LLM Chapters 14.7.4, 22.4.1-22.4.3.
- Week 6: Oct 12 Notes. Read LLM Chapters 14.3, 22.4.1-22.4.3. Optional reading: 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. Oct 14 Notes. Oct 15 Notes. Suggested reading: Apostol: An Elementary View of Euler's Summation Formula. The American Mathematical Monthly 106(5): 409-418, 1999.
- Week 7: Oct 19 Notes. Read LLM Chapters 15.1-15.2. Oct 21 Notes. Oct 22 Notes. Read LLM Chapters 15.3-15.5.
- Week 8: Oct 26 No class (Day following Chung Yeung Festival). Oct 28 Midterm Review. Notes. Oct 29 Midterm Examination.
- Week 9: Nov 2 Notes. Read LLM Chapters 15.7, 15.10. Nov 4 Notes. Read LLM Chapter 15.6. Suggested reading: LLM Chapter 15.8. Nov 5 Notes. Read LLM Chapter 17.
- Week 10: Nov 9 Notes. Nov 11 Notes. Read LLM Chapter 15.9. Nov 12 Notes. Read LLM Chapters 15.9, 16.2.1-16.2.3, 16.2.5.
- Week 11: Nov 16 Notes. Suggested reading: GKP Chapters 5.1, 7.4. Nov 18 Notes. Suggested reading: GKP Chapter 7.5 (Examples 1-4). Nov 19 No class (Congregation).
- Week 12: Nov 23 Notes. Read LLM Chapters 12.1-12.3, 12.7, 12.8.1. Nov 25 Notes. Read LLM Chapters 12.11.1-12.11.2. Optional reading: LLM Chapters 12.11.3-12.11.4. Nov 26 Notes. Read LLM Chapters 12.7-12.8.
- Week 13: Nov 30 Notes. Dec 2 Notes. Read LLM Chapter 12.5. Dec 3 Notes.
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
Last Updated: December 14, 2020