ESTR 2004: Discrete Mathematics for Engineers (ELITE Stream)
2017-18 First Term
Announcements
- NEW: Homework 7 is now posted. It is due on December 11, 2017.
- NEW: The final examination will be held on December 15, 2017. It will mainly cover the material after the midterm; i.e., from the October 23 lecture up to the November 30 lecture. However, you should also be familiar with the material before the midterm. You are allowed to bring one A4-sized cheat sheet. You can write or print on both sides of the cheat sheet. You can also bring a calculator. No other material will be allowed. Please contact the teaching staff if you need any clarification on the rules.
- Here is the midterm solution.
- The Thursday tutorials will be used as lectures. For the tentative class schedule, please see Section 5 of the Information Sheet. The next lecture will be on September 7, 2017.
- 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.
- To better facilitate discussions and Q&As, we have set up an online platform. Please follow this link to sign up.
- PLEASE READ: Student/Faculty Expectations on Teaching and Learning, from the Faculty of Engineering, The Chinese University of Hong Kong.
General Information
- Instructor: Anthony Man-Cho So (manchoso at se.cuhk.edu.hk)
- Office Hours: Thursdays 3:30pm - 5:00pm or by appointment, in ERB 604
- Lecture Time/Location:
- Mondays 10:30am - 12:15pm, in ERB 804
- Wednesdays 1:30pm - 2:15pm, in LHC 106
- Thursdays 10:30am - 12:15pm, in ERB 804
- Teaching Assistants:
- Zengde Deng (zddeng at se.cuhk.edu.hk)
- Office Hours: Wednesdays 3:30pm - 4:30pm, in ERB 810C
- Sen Huang (hsen at se.cuhk.edu.hk)
- Office Hours: Fridays 11:00am - 12:00pm, in ERB 905
- Yuen Man Pun (ympun at se.cuhk.edu.hk)
- Office Hours: Wednesdays 9:30am - 10:30am, in ERB 905
- Peng Wang (wangpeng at se.cuhk.edu.hk)
- Office Hours: Tuesdays 3:30pm - 4:30pm, in ERB 810A
- Xiaolu Wang (xlwang at se.cuhk.edu.hk)
- Office Hours: Tuesdays 10:30am - 11:30am, 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, 2010.
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 2. Sep 7 Notes. Read LLM Chapter 3.1-3.2.
- Week 2: Sep 11 Notes. Read LLM Chapters 3.3-3.4 and (optional) 3.5. Sep 13 Notes. Read LLM Chapters 9.1-9.2. Sep 14 Notes. Read LLM Chapter 9.5. Suggested Reading: GKP Chapter 2.4.
- Week 3: Classes cancelled.
- Week 4: Sep 25 Notes. Suggested reading: GKP Chapters 3.1, 3.2. Sep 27 Notes. Suggested reading: GKP Chapter 2.5. Sep 28 Notes. Suggested reading: GKP Chapters 1.3, 7.2, 7.3.
- Week 5: Oct 2 National Day Holiday. Oct 4 Notes. Read LLM Chapter 10.1.
- Week 6: Oct 9 Notes. Read LLM Chapter 9.7. Oct 11 Notes. Read LLM Chapter 10.4.5. Suggested reading: Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009. Chapter 4.3. Oct 12 Notes. Read LLM Chapters 9.3, 10.4.
- Week 7: Oct 16 Notes. Suggested reading: Knuth. The Art of Computer Programming. Volume 1: Fundamental Algorithms (3rd Edition), Addison-Wesley, 1997. Chapter 1.2.11.2. Oct 18 Notes. Oct 19 Midterm examination.
- Week 8: Oct 23 Notes (updated). Oct 25 Notes. Oct 26 Notes. Read LLM Chapters 11.1-11.5, 11.7, 14.1-14.4.
- Week 9: Oct 30 Notes. Read LLM Chapter 14.1-14.4. Nov 1 Notes. Read LLM Chapter 11.6. Nov 2 Notes. Read LLM Chapter 11.8.
- Week 10: Nov 6 Notes. Read LLM Chapters 11.8. Suggested reading: Brualdi Chapters 2, 6; GKP Chapters 5.1, 5.2. Nov 8 Notes. Nov 9 Notes. Read LLM Chapter 5.1. Suggested reading: GKP Chapters 5.3, 5.4, 7.5.
- Week 11: Nov 13 Notes. Nov 15 Notes. Read LLM Chapter 5.4, 5.5, 5.7. Nov 16 Congregation
- Week 12: Nov 20 Notes. Nov 22 Notes. Read LLM Chapter 5.2. Nov 23 Class cancelled.
- Week 13: Nov 27 Notes. Nov 29 Notes. Suggested reading: West. Introduction to Graph Theory (2nd Edition), Pearson Education, Inc., 2004. Chapter 3.1. Nov 30 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 13, 2017