CS 49/149: 21st Century Algorithms, Fall 2018

Schedule Policies

Course Description and Goals:
The goal of the course is to introduce students to algorithmic ideas relevant for modern day computation problems which are not covered in a typical undergraduate algorithms course (like CS 31). These would include ideas from continuous optimization (like gradient descent), random sampling, sketching, etc. The thrust of the course will be on provable algorithms, and as often happens, the analysis will go hand-in-hand with the design of the algorithms. At the end of the course, the student should be able to read a present-day algorithms publication.

Background Assumed:
Students should have mathematical maturity -- they should be able to read and write proofs, should have a basic understanding of probability, and should be comfortable doing a little analysis (calculus). Please try the problems here to get an idea. It will also help to have taken an algorithms course before for context's sake.

Class Times: 10A (TR: 10:10am - 12noon), X-hours (W: 3:30pm - 4:20pm)
Venue: Sudikoff 115
Discussions: Piazza
Office Hours: Wednesdays, 12:30 - 1:30. Thursdays, 1pm - 2pm, or by email at Sudikoff 216.

Text Books:
There is no textbook, although I will often point out links to material.
For Lectures 1 to 7, most of the material is from (with slight modifications at times)


Tentative Weekly Schedule

The notes below are put on the webpage as is handed in by the scribe. They may contain errors; please let me or the scribe know of any errors.


Lectures, X-hours, Attendence Policy
Please try to attend all lectures; the material covered is advanced and it is easy to fall behind.

Academic Integrity / Honor Code
All work submitted for credit must be your own. This means what you put down on paper for submission cannot be in any way copied from a black/white board, a computer screen, or even your notes from class.
You cannot discuss the drill problem sets with anyone. You may discuss the problem sets with your classmates (taking the course with you), the TAs, and the instructor. No one else. You are also not allowed to give away solutions to your classmates. Clarification questions about problems should be asked on Piazza.
        At the beginning of each problem you must write who you discussed with, and what way did the person help you or you help them. This is important. If you did not talk with anyone about any of the problems, mention this at the beginning of the homework. Any written sources used (apart from the text, your lecture notes and any homework solutions that I distribute) must also be acknowledged; however, you may not consult any solutions on the Internet or from previous years' assignments, whether they are student- or faculty-generated.
        Dartmouth's Academic Honor Principle applies to this course. Please be sure to read the principle, which you can find here . Please ask me if you have any questions about the honor code as it applies to CS 49/149. Better safe than sorry!