CS3000: Algorithms & Data
Time & Location:
2:50pm-4:30pm, MW, West Village G 104
Staff
Instructor: Jonathan Ullman
Office Hours: T 2:30-4:00, 623 ISEC
Teaching Assistant: Danish Farooq
Office Hours: Th 6:00-8:00, 462 WVH
Teaching Assistant: Zachary Galeaz
Office Hours: F 4:00-6:00, 164 WVH
Teaching Assistant: Matthew Jones
Office Hours: Th 4:00-6:00, 462 WVH
Teaching Assistant: Joshua Towner
Office Hours: W 5:00-7:00, 462 WVH
Important Links
Piazza: piazza.com/ccs.neu.edu/spring2020/cs3000/home
Gradescope (Entry Code: 9GZP3P): https://gradescope.com/
Overview
This is an introductory course in algorithms. Although any computer program can be viewed as an implementation of an algorithm for solving a particular computational problem, in this course we focus not on the programs themselves but on the underlying computational problems, and general algorithmic techniques for solving these problems. In this course, we will:
- See a wide range of computational problems arising in different applications
- Learn how to formulate these problems precisely given somewhat informal descriptions
- Learn new algorithmic design techniques used to solve these computational problems
- Learn techniques to prove correctness of algorithms
- Learn techniques to analyze the efficiency of algorithms
- Learn how to transform algorithms to programs
Specific topics typically include:
- Basics tools for analysis of algorithms: proof by induction, asymptotic notation
- Divide-and-conquer algorithms
- Dynamic programming
- Stable matching: the Gale-Shapley Algorithm
- Basic graph algorithms: BFS, DFS, topological sorting, shorest paths
- Network flow algorithms and applications
- NP-completeness
- Greedy algorithms
Last year's course schedule will give you even more of a sense of what is covered in this course.
Discussion Forum: Piazza
We will be using Piazza for class discussion. The system will make it possible to get help quickly and and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I strongly encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email
team@piazza.com.
At the start of the course, I will add everyone on the course roster to Piazza. If you have not been added, please contact me and I will add you.
Textbook
Reading will be assigned mainly from
I feel guilty in this day and age making students pay for textbooks. If obtaining a copy is burdensome, please see me and I can lend you a copy for the semester.
You may find them useful as a reference or as an alternative perspective on some of the material, but they are not required:
Homework Policies
- All homework will be submitted through Gradescope as a PDF.
- All homework solutions must be typeset in LaTeX. I will provide the source files for the HW assignments 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. I 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.
- The lowest homework score will be dropped from your grade.
- I encourage you to work with your classmates on the homework problems. If you do collaborate, you must write all solutions by yourself, in your own words, and are strictly forbidden from sharing any written solutions. You must list all of your collaborators on your submission. The TAs and I reserve the right to ask you explain your solutions.
- No late homework will be accepted. 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 homework score that you drop.
Grading
The final course grade will be computed based on a weighted average of:
- homework (45%)
- two midterms (15% each)
- final exam (25%)