ENGG 2440A / ESTR 2004: Discrete math for engineers

The Chinese University of Hong Kong, Fall 2016

• Instructor
  Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926, office hours Fri 2-4
• Teaching Assistants
  Xin Huang, xhuang (a) cse.cuhk.edu.hk, SHB 117, office hour Tue 10-11
  King On Yung, koyung (a) cse.cuhk.edu.hk, SHB 1005, office hour Wed 3.30-4.30
  Yue Wang, yuewang (a) cse.cuhk.edu.hk, SHB 101, office hour Wed 11-12
  Chris Williamson (Head TA), chris (a) cse.cuhk.edu.hk, SHB 117, office hour Wed 2.30-3.30
  

Recent Announcements

• 16 Dec Here are sample solutions for the final exam.
• 14 Dec The final exam grades are now released. The median grade is 37½ in ENGG 2440A and 60½ in ESTR 2004 (out of 80).
• 14 Dec Please verify that all your grades have been recorded properly and notify us of any inconsistency immediately.

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 5	No class, Inauguration Ceremony
1	Sep 7 Sep 12	Logic	notes; code LLM §1.1, §3
2	Sep 14 Sep 19	Proofs	notes LLM §1
3	Sep 21 Sep 26	Induction	notes; code LLM §5, §6
4	Sep 28 Oct 3	Numbers	notes; code LLM §6, §9
5	Oct 5 Oct 10 Oct 12	Graphs I No class, Chung Yeung Festival	notes LLM §12, §6.4
6	Oct 17 Oct 19	Graphs II	notes LLM §10, §11
	Oct 24	Midterm Exam
7	Oct 26 Oct 31	Sums and asymptotics	notes LLM §14
	Nov 2	No class
8	Nov 7 Nov 9	Recurrences	notes LLM §22
9	Nov 14 Nov 16	Counting I	notes LLM §4, §15
10	Nov 21 Nov 23	Counting II	notes; code LLM §15
11	Nov 28 Nov 30	Polynomials	notes; code
	Dec 12 Dec 14	Final exam review 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 this example).

• Homework 1 (out: Sep 12 | in: Sep 22)
• Homework 2 (out: Sep 26 | in: Oct 6)
• Homework 3 (out: Oct 10 | in: Oct 20)
• Practice Midterm 1 and 2 (out: Oct 17)
• Homework 4 (out: Oct 31 | in: Nov 10)
• Homework 5 (out: Nov 14 | in: Nov 24)
• Homework 6 (out: Nov 28 | in: Dec 8)
• Practice final 1 and 2 (out: Nov 28)

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.30-12.15 in TYW LT and Wed 1.30-2.15 in ERB LT.
• 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:
  • Thu 10.30-11.15 in ERB 408 (AT01, Chris's section)
  • Thu 10.30-11.15 in LHC G06 (AT02, Xin's section)
  • Thu 10.30-11.15 in ERB 706 (AT03, Yue's section)
  • Thu 11.30-12.15 in ERB 706 (AT04, Yue's section)
  • Thu 11.30-12.15 in ERB 408 (AT05, Chris's section)
  • Thu 11.30-12.15 in LHC G06 (AT06, Xin's section)
  • Thu 11.30-13.15 in ELB 308 (ESTR 2004, Andrej's and Kingsley's section)
  
  
• 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 the CU e-learning system [ENGG 2440A | ESTR 2004].

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.