CSE 421: "Introduction to Algorithms" (Autumn 2025)

Welcome to the Autumn 2025 edition of CSE 421! See the links above for more information.

You can find office hour information in Course Staff or Calendar. 

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.

*lectures & sections are 50 minutes, even though calendar shows 1hr.

*The lecture and section material below is based heavily on previous CSE 421 iterations by Robbie Weber and Chinmay Nirkhe.
*Slides were created in keynote (and are best viewed in that format). The converted ppt file has occasional formatting issues.

Lectures

09/24: Logistics; stable matchings (slides: keynote, ppt, pdf)

09/26: More stable matchings (slides: keynote, ppt, pdf)

09/29: Graph traversal; Breadth-First Search (slides: keynote, ppt, pdf)

10/01: BFS, DFS, and applications (bipartiteness testing) (slides: keynote, ppt, pdf)

10/03: DFS and applications (cycle detection, topological sorting) (slides: keynote, ppt, pdf)

10/06: Graph modeling; Greedy algorithms (intro and interval scheduling) (slides: keynote, ppt, pdf)

10/08: Greedy graph algorithms (minimum spanning trees) (slides: keynote, ppt, pdf)

10/10: Greedy graph approximation algorithms (max cut) (slides: keynote, ppt, pdf)

10/13: Divide and Conquer (mergesort, 2D closest pair)(slides: keynote, ppt, pdf)

10/15: Divide and Conquer (runtimes, Strassen's matrix multiplication) (slides: keynote, ppt, pdf)

10/17: Divide and Conquer (Karatsuba's integer multiplication, median finding) (slides: keynote, ppt, pdf)

10/20: Divide and Conquer (median/selection finding) (slides: keynote, ppt, pdf)

10/22: Dynamic Programming (memoization, edit distance) (slides: keynote, ppt, pdf)

10/24: Dynamic Programming (edit distance, knapsack) (slides: keynote, ppt, pdf)

10/27: Dynamic Programming (Bellman-Ford) (slides: keynote, ppt, pdf)

10/29: Dynamic Programming (Bellman-Ford continued) (slides: keynote, ppt, pdf)

11/05: Max Flow and Min Cut (intro) (slides: keynote, pdf)

11/07: Max Flow and Min Cut (Ford-Fulkerson) (slides: keynote, ppt, pdf)

11/10: Max Flow and Min Cut (Ford-Fulkerson continued, and Max Flow-Min Cut theorem) (slides: keynote, ppt, pdf)

11/12: Max Flow and Min Cut (Faster algorithms, and applications) (slides: keynote, ppt, pdf)

11/14: Wrapping up Max Flow & Intro to P, NP, and reductions (slides: keynote, ppt, pdf)

11/17: NP-completeness (slides: keynote, ppt, pdf)

11/19: More NP-completeness (slides: keynote, ppt, pdf)

11/21: More NP-completeness (3-SAT) (slides: keynote, ppt, pdf)

11/24: More NP-completeness (Vertex Cover and 3-coloring) (slides: keynote, ppt, pdf)

11/27: Linear Programming (slides: keynote, ppt, pdf)

12/01: Linear Programming (optimal solutions, and simplex method) (slides: keynote, ppt, pdf)

12/03: Linear Programming (simplex method continued, LP approximation of vertex cover) (slides: keynote, ppt, pdf)

Section

09/25: slides, handout, solutions

10/02: slides, handout, solutions

10/09: slides, handout, solutions

10/16: slides, handout, solutions

10/23: slides, handout, solutions

10/30: slides, handout, solutions

11/06: slides, handout, solutions

11/13: slides, handout, solutions

11/20: slides, handout, solutions

12/04: slides, handout, solutions

Blank homework template that you can use. When compiled, it looks like this.

Homeworks

Homework 1 (due Thursday Oct 2 at 11.59pm): pdf

Homework 2 (due Thursday Oct 9 at 11.59pm): pdf

Homework 3 (due Friday Oct 17 at 10am): pdf

Homework 4 (due Thursday Oct 23 at 11.59pm): pdf

Homework 5 (due Thursday Oct 30 at 11.59pm): pdf

Homework 6 (due Friday Nov 14 at 10am): pdf

Homework 7 (due Friday Nov 21 at 10am): pdf

Homework 8 (due Monday Dec 1 at 10am): pdf

Exams

Midterm: Monday Nov 3, 5.30-7.20pm, ECE 105

Final: Monday Dec 8, 2.30-4.20pm, Gates G20