CS 3000: Algorithms & Data — Fall 2021

Syllabus Tentative Course Schedule

Instructors

Rajmohan Rajaraman Andrew van der Poel

Office Hours (online, all times Eastern)

Rajmohan Rajaraman: TBD
Drew van der Poel: TBD

Teaching Assistants

TBA

Piazza Link Description Textbook Grading Policies Recitations

Lectures

TF 09:50-11:30 Rajaraman
TF 13:35-15:15 van der Poel
TF 15:25-17:05 van der Poel

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 and programming assignments (35%), quizzes (8%), two midterms (16% each), 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.. If recitation capacity allows, they can attend a different recitation in any given week.