This course introduces the fundamental techniques for designing and analyzing algorithms. Topics include asymptotic analysis and recurrences, divide and conquer, graph algorithms, greedy algorithms, dynamic programming, network flow, and the theory of NP-completeness. We will emphasize rigorous reasoning about correctness and running time, and how to choose and adapt algorithmic techniques to solve new problems. The course is proof-oriented and assumes comfort with discrete mathematics and prior programming experience.
CS 1800 (Discrete Structures) and CS 2500 (Fundamentals of Computer Science 1), or equivalent. Please email the instructor if you are unsure whether you meet the prerequisites.
Time/location
Instructor: Prashant Pandey
Contact: Please use Piazza (via direct access from within Canvas) for all questions related to lectures, assignments, and logistics. You can post questions anonymously to other students, or anonymously even to the instructors. Please ask publicly where you can, and help your classmates; use private messages sparingly.
Teaching Assistants: we have a team of 4 awesome TAs
TA office hours: TBD
We use the standard grade scale as a starting point: [93%, 100%] is an A, [90%, 93%) is an A-, and so on. We will add points to each exam and to the final total as needed to curve the grades. Historically this course gives roughly 30% A, 50% B, 20% C, and a small number of lower grades; we will target something similar with the curve.
Please refer to this brief overview of asymptotic notations The Asymptotic Cheat Sheet. This will help you easily follow theoretical analyses in the course.
Homework must be typed and readable. We recommend learning LaTeX and using Overleaf. If you are not familiar with LaTeX, see this introduction. Here's a quick Overleaf tutorial.
Everyone needs to read the Northeastern University Policy on Academic Misconduct.
Working with others is a good way to learn the material and we encourage it. However, there are limits to the degree of cooperation that we will permit. You must limit collaboration to a high-level discussion of solution strategies, and stop short of writing down a group answer. Anything that you hand in must be written in your own words. If you collaborate with other students to discuss a problem and then write your own solution, declare upfront in your write-up the names of all students you collaborated with.
On homework, use of AI tools is allowed but discouraged. Homework is graded on completion, so there is nothing to gain by outsourcing it. The exams and quizzes, which are worth 85% of your grade, are in person and closed to any outside help. The students who let an AI do their homework are the students who struggle on the midterms. Work the problems yourself. That is the point of assigning them.
No outside assistance of any kind, AI or otherwise, is permitted on exams or quizzes.
We do not distinguish between cheaters who copy others' work and cheaters who allow their work to be copied. If you have any questions about what constitutes cheating, please ask first.
Special thanks to Prof. Rajmohan Rajaraman and Prof. Jonathan Ullman, whose lectures, slides, and problem sets from earlier offerings of CS 3000 this course draws on heavily. The course is much better for their work.
Course material is also derived in part from standard algorithms texts, including Kleinberg & Tardos, Algorithm Design, and CLRS, Introduction to Algorithms.