CS 3000: Algorithms & Data — Fall 2020

Syllabus Tentative Course Schedule

Instructors

Kevin Gold Rajmohan Rajaraman Jonathan Ullman Andrew van der Poel

Office Hours (online, all times Eastern)

Kevin Gold: TuF 10:00-11:00
Rajmohan Rajaraman: M 10:00-12:00, F 16:00-18:00
Jon Ullman: Tu 15:15-17:15
Drew van der Poel: W 9:45-11:45

Teaching Assistants

TBA

Canvas Link Piazza Link Lectures Description Textbook Grading Policies Recitations

Lectures

All lectures will be presented as pre-recorded videos. The videos for each lecture would be made available the day of the lecture. To facilitate an interactive discussion of concepts covered in each lecture, the instructors will play the lecture videos during specific time slots on the day of each lecture, discuss concepts, and answer questions during these lecture streams. These lecture stream periods are the following (all times Eastern).

TF 09:50-11:30 (Rajaraman)
TF 13:35-15:15 (Ullman & van der Poel)
TF 15:35-17:05 (Gold)

Course Description

This is an introductory undergraduate course in algorithms. Every computer program can be viewed as an implementation of an algorithm for solving a particular computational problem. The focus of this course is on learning algorithm design techniques for solving the underlying computational problems. We will also look at how algorithms translate to programs, but our emphasis will be on the algorithm design and analysis. In this class, you will

Work on a range of computational problems that arise in diverse applications
Learn how to formulate problems precisely from somewhat informal descriptions
Learn new algorithmic design techniques used to solve the problems
Learn proof techniques critical for reasoning about your algorithms
Learn analysis techniques critical to determine the efficiency of algorithms
Learn how to transform algorithms to programs

Specific topics covered in the course typically include:

Basics tools for analysis of algorithms: proof by induction, asymptotic notation
Divide-and-conquer algorithms
Dynamic programming
Basic graph algorithms: BFS, DFS, topological sorting, strongly connected components
Graph optimization: shortest paths, minimum spanning trees
Amortized analysis, randomized algorithms
Greedy algorithms
Network flow algorithms and applications
NP-completeness

Textbook

Algorithm Design, by Kleinberg and Tardos, Pearson

Grading

Grades will be based on problem sets (30%), programming assignments (10%), quizzes (15%), one midterm (20%), and final (25%). The final grade assigned to a student will be based on the overall performance of the student relative to the entire class.

Policies

All problem sets will be submitted through Gradescope as a PDF.
All problem sets must be typeset in LaTeX. We will provide the source files for the problem sets to help you get started. See below for some advice on LaTeX. Learning LaTeX can take some time, but is well worth the investment, since most technical publications are written in LaTeX. Great editors exist on most platforms. We recommend TexShop for Mac. TeXstudio is a good cross-platform editor. The not so short introduction to LaTeX is a good reference to get you started.
Instructions for submission of programming assignments will be provided with each assignment.
No late homework will be accepted. The lowest problem set score will be dropped from your grade. Extensions will be granted only in rare, extreme, and verifiable circumstances. If you know that you wont be able to get a certain assignment in, plan ahead so that you can use this as the one problem set score that you drop.
Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission.
Finding solutions to homework problems on the web, or by asking students not enrolled in the class is strictly prohibited.

CS 3001 Recitations

Since this is a large class, and the main focus of the course is problem-solving, we will have weekly recitation sessions in which we will work through several problems related to material covered in the lectures.

The recitations will be devoted to problem-solving and answering conceptual questions. The exercises discussed in the recitation during a week will be identical across all the recitations (in-person and online).
Students are required to attend one recitation each week. Each student will be enrolled in a recitation that they can attend (in-person or online, according to their chosen format). If recitation capacity (based on social distancing or online limit) allows, they can attend a different recitation in any given week.
We will certainly make accommodations for students who may need to change their enrollment from in-person learning to remote learning, or the other way, any time during the semester.