Course Mission


You should be familiar with the following topics:

Grading and Requirements

The requirements of the course are as follows:

Homework policy

You are encouraged to discuss the course material and the homework problems with each other in small groups (2-4 people; 4 is an upper limit), but you must list all discussion partners on your problem set. Discussion of homework problems may include brainstorming and verbally discussing possible solution approaches, but must not go as far as writing up solutions together; each person MUST WRITE UP HIS/HER SOLUTIONS INDEPENDENTLY. You may not collaborate with another student on writing up solutions or even look at another student's written solutions. If your homework writeup resembles that of another student in a way which suggests that you have violated the above policy, you may be suspected of academic dishonesty.

You may consult certain outside materials, specifically lecture notes and videos of other classes, any textbooks, and research papers. You may not consult any other materials, including solved homework problems for this or any other class. For all outside materials used, you must provide a detailed acknowledgement of the precise materials used. Whether or not you consult outside materials, you must always write up your solutions in your own words. If your homework writeup resembles any outside source in a way which suggests that you have violated the above policy, you may be suspected of academic dishonesty.

Violation of any portion of this policy will result in a penalty to be assessed at the instructor's discretion. This may include receiving a zero grade for the assignment in question AND a failing grade for the whole course, even for the first infraction.

More generally, students are expected to adhere to the Academic Honesty policy of the Computer Science Department; this policy can be found in full here. Please contact the instructor with any questions.

Re-grade policy:

If you dispute the grade received for an assignment, you must submit, in writing, a detailed and clearly stated argument for what you believe is incorrect and why. This must be submitted no later than one week after the assignment was returned. (For example, if the assignment were returned to the class on Tuesday, your regrade request would have to be submitted before the next Tuesday.) Requests for a re-grade after this time will not be accepted. A written response will be provided within one week indicating your final score. Requests of re-grade of a specific problem may result in a regrade of the entire assignment. This re-grade and written response is final. Keep in mind that a re-grade request may result in the overall score for an assignment being lowered.


The textbook for this course is:

This book is available for purchase on-line. It's also available on reserve in the science and engineering library, and is electronically available through the Columbia library here (you will need to be signed in to access this). Note that several topics which we'll cover (particularly early in the semester) are not in the book. Here are some good sources for some of the material which we will cover in the first few weeks of class:

An overview of Chernoff and Hoeffding bounds can be found here (thanks to Clement Canonne for preparing this).

For the unit on boosting, a good reference is Rob Schapire's survey paper "The Boosting approach to machine learning: An overview". The first three sections give a (very condensed) treatment of the AdaBoost algorithm we'll cover in class, and later sections have good overviews of more advanced material. The original paper on Adaboost, "A decision-theoretic generalization of on-line learning and an application to boosting", is a good sources as well. Click here for a handy copy of the AdaBoost algorithm.

Guidelines for Online Community

Please keep your microphone muted unless you have been called on to answer a question. You are encouraged to ask questions during lecture! The smoothest way to do this is to signal that you have a question in Zoom Chat, and then the TA who is handling the course chat will either answer your question or bump it up to Rocco.

If possible, please keep your camera on during class - this is to promote engagement and community within the class as much as possible.

It's important that we keep our online interactions inclusive, supportive, and positive.


Here are some snippets of advice which are informal, but will hopefully help you get the most out of this class: