# ENGG 2440A: Discrete math for engineers

The Chinese University of Hong Kong, Fall 2017
• Instructor
Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926, office hours Mon 2.30-4.30
• Teaching Assistants
Huang Xin, xhuang (a) cse.cuhk.edu.hk, SHB 117, office hour Tue 11-12
Shao Han, hshao (a) cse.cuhk.edu.hk, SHB 1024, office hour Fri 2-3
Yung King On, koyung (a) cse.cuhk.edu.hk, SHB 117, office hour Wed 3.30-4.30
Chris Williamson (Head TA), chris (a) cse.cuhk.edu.hk, SHB 117, office hour Wed 2.30-3.30

## Recent Announcements

• 20 Dec Please verify your grades on blackboard and let us know if there is any discrepancy.
• 20 Dec The final exam median grade is 31 (out of 70) and the standard deviation is 14.
• 18 Dec Here are the final exam solutions.
• 14 Dec There was a mistake in the solution in question 3b of Homework 6. It is now fixed. If yours was misgraded please see your TA or email them with a picture of the relevant solution.

## 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 4 No class, Inauguration Ceremony
1Sep 6
Sep 11
Logic notes
LLM §1.1, §3
2Sep 13
Sep 18
Proofs notes
LLM §1
3Sep 20
Sep 25
Induction
notes; code
LLM §5, §6
4Sep 27
Oct 4
Numbers notes; code
LLM §6, §9
5Oct 9
Oct 11
Graphs I
notes
LLM §12, §6.4
6Oct 16
Oct 18
Graphs II
notes
LLM §10, §11
Oct 23
Oct 25
Midterm Exam solutions
7Oct 30
Nov 1
Sums and asymptotics
notes
LLM §14
8Nov 6
Nov 8
Recurrences notes
LLM §22
9Nov 13
Nov 15
Counting I notes
LLM §4, §15
10Nov 20
Nov 22
Counting II notes; code
LLM §15
11Nov 27
Nov 29
Probability notes
LLM §17
Dec 13
Dec 15
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.

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.

## Course Information

• Lecture times Mon 10.30-12.15 in YIA LT3 and Wed 1.30-2.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 before each lecture. Please arrive on time and remember to touch your CULink card.
• 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 (Chris's section): Thu 10.30-11.15 in ERB 408
• AT02 (Chris's section): Thu 11.30-12.15 in ERB 408
• AT03 (Xin's section): Thu 10.30-11.15 in ERB 713
• AT04 (Xin's section): Thu 11.30-12.15 in ERB 713
• AT05 (Kingsley's section): Thu 10.30-11.15 in ERB 706
• AT06 (Han's section): Thu 11.30-12.15 in ERB 706

• 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.