This is an undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. As with all CIM subjects, the emphasis is on communication, both oral and written. Enrollment is limited by the department.
In this spring, we will cover various mathematical topics in theoretical computer science, with a focus on approximation algorithms.
Announcements
Apr 26: deadline for your term paper is set to be May 13, 11.59pm.
Apr 4: Problem Set 2 is revised.
Mar 23: deadline for the draft of your term paper is set to be April 24, 11.59pm.
Mar 22: Problem Set 2 is posted. The deadline is before April 20, 11.59pm.
Mar 11: Problem 2(d) in Problem Set 1 is revised. Deadline for Problem Set 1 is extended to 11.59pm on March 20.
Feb 16: Problem Set 1 is revised.
Feb 11: Problem Set 1 is posted. The deadline is before March 15, 11.59pm.
Feb 3: a tentative schedule is posted.
Jan 20: course information and a tentative list of topics are posted.
Course Information
Instructor: Yuan Zhou.
Office Hours: By appointment.
Prerequisite. A course in algorithms at the level of 6.046.
Google group. Students will be added to a google group for course announcements and discussions after the first class.
References. The course will mainly follow the lecture notes of the great course by Ryan O'Donnell.
Additional references are also listed after each topic.
Evaluation Scheme.
Students will be expected to give 2~3 45-minute presentations in class throughout the semester (45%) and hand in a final project (20%).
Additionally, there will be two problem sets (10% * 2 = 20%)
as well as grades for in-class participation (15%).
Presentations.
At the end of this page is the set of proposed topics.
At the beginning of the semester, each student will choose to study 2 topics (while each topic is to be chosen by 2 students).
For each topic, the 2 relevant students will collaborate and give an in-depth presentation over 2 (or possibly 3) 45-minute sessions.
Presentation Tips.
Many of the materials are quite challenging. So please prepare for your presentation early and allocate enough time for your study.
The materials in the topic list are sometimes more than enough for your presentation. Please make your own selection so that you do not run out of time. You may also present other related topics upon consulation with me.
You may send me a brief outline before your lecture, and discuss either via email or face-to-face with me on the topics you select. This is not mandatory, but very encouraged.
At the end of each presentation, each of the audiences will fill out an anonymous feed-back form and you may use the suggestions in the forms to improve your future presentations.
Problem Sets.
Each problem set will contain ~5 questions. The answers must be typesetted in PDF format (and preferably via LaTeX) and submitted to the instructor's e-mail address. A LaTeX template for your answers can be found here.
Problem Set Collaboration Policy.
Students are encouraged to discuss and work in groups on problem sets.
However students must state the people they discussed with in the acknowledgement section of their written assignment.
Students are not allowed to take detailed notes in any group discussion that will appear verbatim in assignment write-ups. Every student has to turn in answers that are written solely by himself/herself.
Term Paper.
The term paper is to be a 4-6 page essay on a topic related to the course.
The goal is for you to explain a topic (preferrably one that you gave a presentation on) clearly to others in the class, or better, to other upper-class math majors.
The paper must be written in a professional style, and formatted in AMS-LaTeX, like the papers in MIT's Undergraduate Journal of Mathematics;
please click here for some helpful resources.
Deadlines.
Problem Set 1 is due at March 15 March 20, 11.59pm.
Problem Set 2 is due at April 20, 11.59pm.
A draft of at most 2 pages is due at April 24, 11.59pm.
It should contain a high level outline of the entire paper.