CSE 421: "Introduction to Algorithms" (Autumn 2025)
CSE 421: "Introduction to Algorithms" (Autumn 2025)
Course Description
The course introduces the design and theory of algorithms. Covers several algorithmic paradigms, including greedy algorithms, divide and conquer algorithms, linear programming, and dynamic programming through a series of optimization and graph problems. Explores techniques to identify and handle intractable problems, including the concepts of NP-hardness and NP-completeness.
This is a proof-based course that focuses on how different algorithms work, how to prove their correctness, and how to design an algorithm when given a new problem to solve. There is almost no coding (mostly algorithm design in pseudocode and proofs), and the emphasis is on conceptual understanding of common algorithms and tools to explain why algorithms are correct.
Prerequisites: CSE 312, 332. Math 208 is strongly encouraged.
Course Goals
The goal for the end of the course is that you will be able to:
Model word problems as computational problems.
Determine an appropriate algorithm design paradigm for a new problem.
Design an algorithm using a variety of algorithm-design paradigms (including greedy algorithms, divide and conquer, dynamic programming, flow modeling, and others).
Prove your algorithm produces the correct answer.
Reduce between a new problem and a known problem (for showing hardness or for reusing existing algorithms)
Identify and cope with computational problems that are infeasible.
Consider the implications of modeling decisions in the real world.
Logistics
Communication: on Ed Discussion. You should have received an invitation to join (let Andrea know if not).
Homework submissions: on Gradescope.
Lecture recordings: lectures will be recorded, and available on Canvas.
Office hours: info in Calendar or Course Staff.
Exams: there will be 1 midterm and 1 final. Date and location in Exams.
Grading
There will be 8 homeworks, 1 midterm, and 1 final. The grade for the class will be determined based on a weighted average of homeworks and exams as follows: 50% homeworks, 22% midterm, 28% final.
Other Resources
All of the required content for this class can be obtained from lectures and sections. However, the following optional textbook is great, and may provide another perspective: "Algorithm Design" by Jon Kleinberg and Éva Tardos, Addison-Wesley, 2006.
You can find some useful review material relating to CSE 332 here.
Here is a style guide for writing your solutions for this class.
This course is heavily based on previous CSE 421 iterations by Robbie Weber and Chinmay Nirkhe, which you may also find useful.
Late submissions
You have 6 tokens for 24 hours late submission of homeworks, no questions asked (you may use up to 3 on each homework). After the 6 tokens are used, homeworks submitted up to 24 hours late are graded with a 50% penalty, and homeworks submitted after 24 hours will not be counted for credit. Extenuating cirumstances are of course separate, and should be discussed directly with Andrea.
Collaboration and use of external resources (including AI)
Collaboration with other classmates is encouraged! However, we ask that you write up your solutions individually, and mention your collaborators at the start of your homework solutions.
You can use AI or external resources to clarify concepts from class, or concepts that you are not familiar with, but you are not allowed to use AI or external resources to directly look for the answer to a homework question. We understand that when searching for general information you may accidentally find the exact question we asked. In such cases, we ask that you tell the staff, and provide a link to what you found (if you do so, this will not count as a violation of the policy).
If you are unsure about whether something is allowed, please feel free to ask Andrea.
Academic Integrity
The goal of our assignments is for you to fully understand and internalize the content of the course. Working through homework problems is an integral part of developing this understanding (I firmly believe that there is no substitute to this for learning!). The policies above are designed for you to go through this crucial part of the learning process.
Not following these policies will likely detract from your learning, and it directly negatively affects other students who are following them, since grades are determined partly based on relative performance. Therefore, we take academic integrity seriously. We refer violations of departmental policies to the Office of Academic Affairs. If you are found responsible for a violation of academic integrity on a homework problem, you will receive a 0 on the relevant problem.
I understand that sometimes life can get in the way of spending as much time as you'd like to on assignments. I hope the 6 late tokens can help mitigate busy or stressful times. You should always feel free to reach out directly to Andrea for extra help on the class material (I'm available!), or if there are extenuating circumstances. We can figure something out.