**Instructor**

Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926, office hours Fri 2-4**Teaching Assistants**

Ken Leung, cyleung (a) cse.cuhk.edu.hk, SHB 117, office hour Tue 1.30-2.30

Peter Poon, cypoon (a) cse.cuhk.edu.hk, SHB 117, office hour Thu 3-4

Gary Sham, yhsham (a) cse.cuhk.edu.hk, SHB 117, office hour Wed 2-3

Chris Williamson, chris (a) cse.cuhk.edu.hk, SHB 117, office hour Mon 1-2

Hong Zhou (*Head TA*), hzhou (a) cse.cuhk.edu.hk, SHB 117, office hour Thu 11-12

**16 Dec**Here are the solutions to the practice final exam.**11 Dec**The final exam review session will take place on Mon Dec 15 from 6.30 to 8.30 in SC L5.**11 Dec**In question 4 of the practice final, assume the graph does not have a source. (Updated at 2.10am.)**8 Dec**A practice final exam is posted. The final exam will have the same format.**1 Dec**The final exam will be like the midterm but with 8 questions. You can bring in unannotated printouts of the lectures and*two*sheets of handwritten notes.**1 Dec**The Final Exam will take place on Wed Dec 17 from 12.30 to 14.30 in the University Gymnasium.

This course is about mathematical models 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 "recipes" for calculating answers and learn how to argue convincingly that your solution to a given problem is sensible.

date | topic | readings | ||
---|---|---|---|---|

Sep 1 | No class, Inauguration Ceremony |
|||

1 | Sep 2 Sep 8 |
Logic | LLM §1; notes | |

Sep 9 | No class, Mid Autumn Festival |
|||

2 | Sep 15 Sep 16 |
Proofs | LLM §2; notes | |

Sep 22 Sep 23 |
No class |
|||

3 | Sep 29 Sep 30 |
Induction | LLM §3; notes; code | |

4 | Oct 6 Oct 7 |
Number theory | LLM §4; notes; code | |

5 | Oct 13 Oct 14 |
Graphs I | LLM §5; notes | |

6 | Oct 20 Oct 21 |
Graphs II | LLM §5, §6; notes | |

Oct 27Oct 28 |
Midterm Exam |
|||

7 | Nov 3 Nov 4 |
Sums and asymptotics | LLM §9; notes | |

8 | Nov 10 Nov 11 |
Recurrences | LLM §10; notes | |

9 | Nov 17 Nov 18 |
Counting I | LLM §7.2, §11; notes | |

10 | Nov 24 Nov 25 |
Counting II | LLM §11; notes; code | |

11 | Dec 1 Dec 2 |
Polynomials | notes; code | |

Dec 17 |
Final exam |

Homeworks will be issued every other week according to the following schedule:

**Tuesday:**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.**Friday 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 Friday 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 Friday tutorial. No late submissions will be accepted. Please read the CUHK policy on honesty in academic work.

- Homework 1 (out: Sep 9 | in: Sep 19) |
- Homework 2 (out: Sep 23 | in: Oct 3) |
- Homework 3 (out: Oct 7 | in: Oct 17) |
- Practice Midterm 1 and 2 (out: Oct 21) |
- Homework 4 (out: Oct 28 | in: Nov 7) |
- Homework 5 (out: Nov 11 | in: Nov 21) |
- Homework 6 (out: Nov 25 | in: Dec 5) |
- Practice final (out: Dec 8) |

You can use the ENGG 2440A discussion board on the CU e-learning system to ask questions and participate in online discussions related to the course.

**Lecture times**Mon 9.30-11.15 and Tue 11.30-12.15 in Lady Shaw Building LT1.**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:- Chris's section, Fri 9.30-10.15 (F2), ERB 401
- Peter's section, Fri 9.30-10.15 (F2), ERB 405
- Zhou Hong's section, Fri 9.30-10.15 (F2), ERB 706
- Ken's section, Fri 1.30-2.15 (F6), ERB 402
- Gary's section, Fri 3.30-4.15 (F6), ERB 402

**Textbook**The primary reference for this course is*Mathematics for Computer Science*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.