In this course, students will get familiar with combinatorics through selected exciting ideas in theoretical computer science (in particular, algorithms and complexity). This is a class that spans over 6 weeks only, so it is relatively intensive. Please try to minimize your other workload when taking this class.
New Schedule (14.05-07.06):
- Tutorial Session: Monday (14 May), 17 - 19, Room A106.
- Lecture: Wednesday (16 May), 12:15-13:45, Room T4.
- Exercise sheet 5: deadline Wednesday (23 May), 23:55.
- Final exam: deadline Thursday (14 June), 23:55.
First meeting: April 11, 2018
Lectures: Wednesday, 12:15 - 13:45. Room T4
Tutorials and Q&A sessions: Thursday, 16:15 - 18:45. Room T4
- Prof. Parinya Chalermsook (responsible teacher) - Office hours: Every Friday, 13:30 - 14:30. Room B305.
- Dr. Sumedha Uniyal - Office hours: Every Tuesday, 14:30 - 15:30. Room B311.
Prerequisite: Mathematical maturity. In particular, the ability to read and write basic mathematical proofs. Familiarity with the asymptotic analysis in discrete mathematics would make your life much easier in this course.
Intended Learning outcomes: (i) Students are familiar with the basic concepts of graph theory, discrete probability, analysis of boolean functions, and linear algebra. (ii) Students are able to apply some of these concepts to address questions arising in computer science.
There will be no in-class exam. Your grades will be determined by problem sets and take-home exams. The total number of points is 100 (plus some possible bonus). If you get the score of at least 70, it will guarantee Grade 5. The score of at least 30 in total would guarantee to pass the course.
Basic math problem sets (50 points): Handed out every Thursday in the exercise session, due on subsequent Wednesday at noon. The solutions to the problem sets can either be uploaded on MyCourses or can be handed over to the lecturer right before the lecture. There will be some bonus points for attending each tutorial session. You are encouraged to discuss the basic problem sets with your classmates, but make sure you write down the solutions by yourself. To be eligible for submitting the take-home exams, you would need at least 25 points from the basic problem sets.
Take-home exams on CS problems (50 points): There will be 5 exam sets on different CS topics covered in class. You need to submit the solutions to ONLY 2 exam sets by May 31. The take-home exam does not have a time limit, so spend as many hours as you like; just make sure that you submit it on or before May 31. Each exam set carries 25 points.
You are supposed to work on take-home exams on your own. Please do not consult any external source, except the lecture notes handed out in this class. Do not Google for the solutions.
Class sessions & Expectation:
There will be 2 meetings per week.
Lectures on Wednesday, 12:15 to 14:00. There will be 6 meetings in total. The lecturer will explain the applications of combinatorics in computer science.
Tutorial on Thursday, 16:00 to 19:00. This is a 3-hour meeting. There will be 5 meetings in total. One of the lecturers will spend the first half covering basic concepts in combinatorics that would be relevant to the class. In the second half, exercises will be handed out, and the students may collaborate on exercises as well as asking the lecturer for hints and clarifications.
Office hours on Tuesday: There will be a 1-hour office hour held by either one of the instructors. Please stop by to ask anything!
The meetings take 25 hours in total. Students are expected to spend additional 40 hours working on homework problems. Collaborations on basic problem sets are strongly encouraged. Also, each student is expected to spend additional 60 hours on the take-home exams.
There will be 5 class modules. Each module starts on Thursday and ends on Wednesday the following week. Here is a learning guideline:
The purpose of the Thursday session is to make sure that students have sufficient background to follow the lecture on Wednesday.