This course showcases how different areas of mathematics can be useful in computer science. We will study several mathematical tools such as Algebra (Fields, Polynomials), Matrix theory, (Discrete) Probability, Fourier analysis, and see how they are used in developing modern algorithms and proving impossibility results in various areas in computer science.
This covers some of the basic tools that would be useful for students who are interested in doing research in the theory side of computer science.
You are expected to be familiar with basics in Discrete Math (CSC 226), Data structures and Algorithms (CSC 316). In particular, it is important to refresh your memory on the following concepts before coming to class:
The free book "Mathematics for Computer Science" by Lehman, Leighton, and Meyer is an excellent resource for learning these concepts. It also comes with a set of online lectures.
Notes and references will be provided.
Class attendance is expected but not mandatory. Any of the following activities can be counted towards class participation:
Questions will be regularly posted as individual threads on Ed. Everyone can answer and comment on any question except the designated ones (see next paragraph). Any well-thought-out (possibly incorrect) answer will count towards your homework grade. To keep your comments clear and concise, you should prepare them in draft on your own beforehand. Your homework grade will be periodically updated on Moodle.
Some questions are assigned to students who are less active. If you are assigned such a question, you have 5 days (excluding weekend) to respond with an answer to that thread. If you spend some reasonable amount of time and cannot make any progress, you should comment to the thread as soon as you can so that I can provide appropriate hints to guide you towards a solution. Start early -- your grade for a question will be determined on day 5 (unless late days are applied).
Homework policy:
Each student has a total of 4 late days for their assigned questions for the whole semester, of which you can use up to 2 days (including weekend) on any question. Each late day is exactly 24 hours and cannot be subdivided, e.g. a 5-minute late is counted as 1 late day.
No request is required for these 4 late days, but any extension request beyond them will be subject to Academic Absence Verification. Any answer submitted more than 7 days after a question is posted will not receive any homework grade.
If you rely on the assistance of an AI or others in class, you are solely responsible for any resulting mistakes.
Exam policy:
Exam must be taken in-person and cannot be taken virtually. Any rescheduling request will be subject to Academic Absence Verification.
Regrade policy:
If you dispute the grade received for an exam question, you must submit, in writing through Gradescope, a detailed and clearly stated argument for what you believe is incorrect and why, within 5 days after the exam was returned to you.
Requests of regrade of a specific problem may result in a regrade of the entire assignment. This regrade and written response is final. Keep in mind that a regrade request may result in the overall score for an assignment being lowered.
The project consists of a report and a 15-min presentation. Your project report should be about at most 5-page long. If it exceeds 5 pages, the first 5 pages will be read but the rest may not.
More details will be announced after census day when the enrolment number has stabilized.
The following tentative schedule is subject to change according to the pace and interest of the class.
| Lecture | Date | Topics | |
|---|---|---|---|
| 0 | 1/7 (Tue) | Hashing | |
| 1 | 1/9 (Thu) | Hashing | |
| 2 | 1/14 (Tue) | Min-cut | |
| 3 | 1/16 (Thu) | Min-cut | (day before Census day) |
| 4 | 1/21 (Tue) | Streaming algorithms | |
| 5 | 1/23 (Thu) | Streaming algorithms | |
| 6 | 1/28 (Tue) | Property Testing | |
| 7 | 1/30 (Thu) | Property Testing | |
| 8 | 2/4 (Tue) | Property Testing | |
| 9 | 2/6 (Thu) | Property Testing | |
| 2/11 (Tue) | Wellness Day (No class) | ||
| 10 | 2/13 (Thu) | High-dimensional data compression | |
| 11 | 2/18 (Tue) | High-dimensional data compression | |
| 12 | 2/20 (Thu) | Error-correcting codes | |
| 13 | 2/25 (Tue) | Error-correcting codes | |
| 14 | 2/27 (Thu) | Midterm exam | |
| 15 | 3/4 (Tue) | Error-correcting codes | |
| 16 | 3/6 (Thu) | Error-correcting codes | (Project proposal due) |
| 3/11 (Tue) | Fall break (No class) | ||
| 3/13 (Thu) | Fall break (No class) | ||
| 17 | 3/18 (Tue) | Expanders | |
| 18 | 3/20 (Thu) | Expanders | |
| 19 | 3/25 (Tue) | Expanders - Applications | |
| 20 | 3/27 (Thu) | Expanders - Applications | |
| 21 | 4/1 (Tue) | Communication Complexity | |
| 22 | 4/3 (Thu) | Communication Complexity | |
| 23 | 4/8 (Tue) | Communication Complexity | |
| 24 | 4/10 (Thu) | Communication Complexity | |
| 25 | 4/15 (Tue) | Communication Complexity | |
| 26 | 4/17 (Thu) | Presentation | |
| 27 | 4/22 (Tue) | Presentation |
References will be provided throughout the course. Some of the material are taken from the following textbooks and lecture notes: