# CS 3000: Algorithms & Data — Fall 2021

## SyllabusTentative Course Schedule

#### Office Hours (online, all times Eastern)

• Rajmohan Rajaraman: TBD
• Drew van der Poel: TBD

#### 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

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.