CS 3000: Algorithms & Data — Fall 2020
Instructors
Office Hours (online, all times Eastern)

Kevin Gold: TuF 10:0011:00

Rajmohan Rajaraman: M 10:0012:00, F 16:0018:00

Jon Ullman: Tu 15:1517:15

Drew van der Poel: W 9:4511:45
Teaching Assistants
Lectures
All lectures will be presented as
prerecorded 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:5011:30 (Rajaraman)
 TF 13:3515:15 (Ullman & van der Poel)
 TF 15:3517: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
 Divideandconquer 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
 NPcompleteness
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
crossplatform
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
problemsolving, 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 problemsolving and
answering conceptual questions. The exercises discussed in the
recitation during a week will be identical across all the recitations
(inperson and online).
 Students are required to attend one recitation each week. Each
student will be enrolled in a recitation that they can attend
(inperson 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 inperson learning to remote learning,
or the other way, any time during the semester.