ESTR 2004: Discrete Mathematics for Engineers (ELITE Stream)
2019-20 First Term
Announcements
- NEW: Homework 6 is now posted. It is an optional extra credit homework and is due at 11:59pm on December 20, 2019. No late submissions will be entertained.
- NEW: The University announced the ending of Term 1 on November 13, 2019. Please refer to the online forum for the assessment arrangements.
- Here is the midterm solution.
- 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 2440A. In particular, we will not cover LLM Chapters 1 and 2. Interested students can 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: Tuesdays 3:30pm - 5:00pm or by appointment, in ERB 604
- Lecture Time/Location:
- Mondays 10:30am - 12:15pm, in LSB LT3
- Wednesdays 1:30pm - 2:15pm, in ERB 803
- Thursdays 10:30am - 12:15pm, in ERB 803
- Teaching Assistants:
- Jiajin Li (jjli at se.cuhk.edu.hk)
- Office Hours: Mondays 2:30pm - 4:00pm, in ERB 905
- Xiaolu Wang (xlwang at se.cuhk.edu.hk)
- Office Hours: Wednesdays 2:30pm - 4:00pm, in ERB 905
- 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 (30%)
- Essay (15%)
Primary Text
The primary text for this course is Eric Lehman, F. Thomson Leighton, Albert R. Meyer (LLM), Mathematics for Computer Science, 2017.
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 4 Information Sheet, Notes. Familiarize yourselves with the material in LLM Chapters 1 and 2. Sep 5 Notes. Read LLM Chapter 5.1.
- Week 2: Sep 9 Notes. Read LLM Chapters 5.2-5.3, 14.1. Sep 11 Notes. Read LLM Chapters 14.1-14.2. Suggested Reading: GKP Chapter 2.3. Sep 12 Notes (from 2017-18 Term 1). Read LLM Chapter 14.6. Suggested Reading: GKP Chapter 2.4.
- Week 3: Classes cancelled.
- Week 4: Sep 23 Notes. Suggested reading: GKP Chapters 3.1, 3.2. Sep 25 Notes. Sep 26 Notes. Suggested reading: GKP Chapters 1.3, 2.5.
- Week 5: Sep 30 Notes. Read LLM Chapters 16.1, 16.3, 16.4. Oct 2 Notes. Oct 3 Notes. Read LLM Chapter 14.7.
- Week 6: Oct 7 Chung Yeung Festival. Oct 9 Notes. Read LLM Chapter 22.4. Suggested reading: Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009. Chapter 4.3. Oct 10 Notes. Read LLM Chapter 14.3, 22.4.
- Week 7: Oct 14 Notes. Read LLM Chapter 15.1. Suggested reading: Apostol: An Elementary View of Euler's Summation Formula. The American Mathematical Monthly 106(5): 409-418, 1999. Oct 16 Notes. Read LLM Chapter 15.2. Oct 17 Notes. Read LLM Chapters 15.2-15.5.
- Week 8: Oct 21 Notes. Read LLM Chapters 15.5-15.7, 15.10. Oct 23 Notes. Oct 24 Midterm Examination.
- Week 9: Oct 28 Notes. Read LLM Chapters 17.1-17.4, 17.5.1, 17.5.3. Oct 30 Notes. For the optimality of the strategy introduced in class, see Buchbinder et al: Secretary Problems via Linear Programming. Mathematics of Operations Research 39(1): 190-206, 2014. Oct 31 Notes. Read LLM Chapter 15.9.
- Week 10: Nov 4 Notes. Suggested reading: GKP Chapters 7.4-7.5. Nov 6 Notes. Suggested reading: GKP Chapter 7.5, Example 4. Nov 7 Congregation.
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 7, 2019