ENGG 2440A / ESTR 2004: Discrete math for engineers
The Chinese University of Hong Kong, Fall 2018
 Instructor
Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926, office hours Mon 2.304.30
 Teaching Assistants
Ho Chin Hei, chho@cse.cuhk.edu.hk, SHB 101
Ma Kaili, klma@cse.cuhk.edu.hk, SHB 122
Chris Williamson, chris@cse.cuhk.edu.hk, SHB 117
Yung King On (head TA), koyung@cse.cuhk.edu.hk, SHB 117
Zhao Zixu, zxzhao@cse.cuhk.edu.hk, SHB 1024
Recent Announcements
 7 Dec Here are sample solutions for the practice finals.
 5 Dec Here are the notes for lectures 15 and 611 that you can bring to the exam.
 5 Dec There will be a review on Fri Dec 7 at 6.30pm in LSK LT2 (confirmed). We will go over the practice exams and you can ask to go over any part of the material.
 2 Dec The final exam will consist of 7 questions and cover Lectures 111 just like these practice exams. You can bring in the lecture notes (without annotations) and one doublesided sheet of handwritten notes.
 2 Dec Homework 6 is optional. If you turn it in, you can use it to replace your lowest grade on the previous homeworks. Please drop it off in the collection box by 12 noon on Mon 10 Dec.
Course Description
This course is about mathematical concepts and techniques that are helpful for describing, analyzing, and solving problems in computer science. There will be much emphasis on proofs and rigorous reasoning.
To be successful in discrete mathematics, you will need to go beyond memorizing recipes for calculating answers and learn how to argue convincingly that your solution to a given problem is sensible.
Schedule

date 
topic 
materials 
 Sep 3 
No class, Inauguration Ceremony 

1  Sep 5 Sep 10 
Logic 
notes; code LLM §1.1, §3 
2  Sep 12 Sep 19 
Proofs 
notes LLM §1 
3  Oct 2 Oct 3 
Induction

notes; code LLM §5, §6 
4  Oct 8 Oct 10 
Numbers 
notes; code LLM §6, §9 
5  Oct 15 Oct 22 
Graphs I

notes LLM §12, §6.4 
6  Oct 24 Oct 31 
Graphs II

notes LLM §10, §11 
 Oct 29 
Midterm Exam 
solutions 
7  Nov 5 Nov 7 
Sums and asymptotics

notes LLM §14 
8  Nov 12 Nov 14 
Recurrences 
notes LLM §22 
9  Nov 19 Nov 21 
Counting I 
notes LLM §4, §15 
10  Nov 26 Nov 28 
Counting II 
notes; code LLM §15 
11  Dec 3 Dec 5 
Probability 
notes LLM §17 
 Dec 11 
Final exam 


Tutorials and homeworks
Homeworks will be issued every other week according to the following schedule:
 Monday: A homework consisting of 6 problems is posted here. Ten days later in tutorial, you will need to turn in solutions to 4 out of these 6 problems of your choice.
 Thursday tutorial: You discuss the homework problems in groups. Feel free to ask your TA for advice and help. You may volunteer to present your solution.
 Next Thursday tutorial: The TA will collect homework solutions. Then some of you will be asked to present your solution to the class. Students will be chosen randomly with repetition. This means you may be called to present at any time, and more than once.
Come to tutorial prepared. Your participation and the quality of your presentation will count towards your grade. If you cannot make it on any particular week, let your TA know in advance.
You are encouraged to collaborate on homeworks, but you must write up your own solutions and list your collaborators on the solution sheet. You will hand in the solutions to your TA at the beginning of Thursday tutorial. No late submissions will be accepted. Please read the CUHK policy on honesty in academic work and see these slides about ENGG 2440A in particular.
Discussion board
There is an ENGG 2440A discussion board on piazza. Please register and sign in using your CUHK email address.
Course Information
 Lecture times Mon 10.3012.15 in Science Centre LT and Wed 1.302.15 in ERB LT.
 Attendance The Faculty of Engineering requires that every
student attends at least half the lectures of ENGG 2440A. Attendance
will be taken electronically via KEEPoll. Sick days will not be discounted
(if you are on extended sick leave please contact me).
 Tutorials Tutorial attendance and participation will count towards your grade. You are required to attend the same tutorial section every week. The tutorial times are:
 AT01 (Zhao Zixu): Thu 10.3011.15 in ERB 713
 AT02 (Yung King On): Thu 11.3012.15 in ERB 713
 AT03 (Ho Chin Hei): Thu 10.3011.15 in ERB 706
 AT04 (Ma Kaili): Thu 11.3012.15 in ERB 706
 ESTR 2004 lecture + tutorial (Andrej + Chris): Thu 10.3012.15 in
ERB 408 SHB 904
 Textbook The primary reference for this course is Mathematics for Computer Science [download 13MB] by Lehman, Leighton, and Meyer (LLM). Notes will be provided for material not covered in the textbook.
 Grading Your grade will be determined
from a midterm exam (25%), a final exam (40%), homework solutions
(15%), and attendance, participation, and homework presentation (20%).
You can verify our record of your grades on CUHK blackboard.
ESTR 2004 students
ESTR 2004 follows the same format as ENGG 2440A, but with additional readings and supplementary homework. Generally, ESTR 2004 students will be held to a higher standard for tutorial discussions and homework presentation (both oral and written).
 Readings You will be assigned additional reading material (starred in the lecture notes) each week. You are expected to come to tutorial prepared to discuss these readings, initiating questions if anything is unclear, and apply them towards the homework.
 Homeworks You will be given an additional project exercise in your homework. This exercise is mandatory; it may require a bit of initiative and independent research on your part. Some of them will involve computer work including programming (in any language of your choice).
 Exams and grading The grading policy is the same as for ENGG 2440, but the grade cutoffs may be different to account for the relative difficulty of ESTR 2004. (For instance, a final score of 83 out of 100 may end up being a B+ in ENGG 2440A but an A in ESTR 2004.) Exams will have the same format as in ENGG 2440, but some questions will be modified to test for the supplementary material.