Introduction to Algorithms

CSE 421 | Spring 2025

Course Logistics

Instructor: Chinmay Nirkhe (OH: TBD, CSE2 217)
Course Staff: Click here
Location: Gates 20
Times: M, W, F 3:30 - 4:20 pm
Recitation section: see time table
Midterm: May 3rd 3:30 - 4:20
Final: June 12th 2:30 - 4:20
Canvas: TBD
Gradescope: TBD

Catalog description

Catalog Description: Techniques for design of efficient algorithms. Methods for showing lower bounds on computational complexity. Particular algorithms for sorting, searching, set manipulation, arithmetic, graph problems, pattern matching. Prerequisite: CSE 312; CSE 332.

Course goals

CSE 421 is an introduction to algorithms. By the end of this course, 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 that your algorithm produces the correct answer.
• Reduce between a known problem and a new 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.

Communication is a key aspect of this course. It is not enough to write code that works, you will also need to convince others that your code will work!

Textbook

This iteration of the course uses "Algorithm Design" by Jon Kleinberg and Éva Tardos, Addison-Wesley, 2006 and "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, McGraw-Hill Higher Education, 2006.

Lectures

Lectures will be given in person. They will be recorded for later review but this ability should not be used to substitute for in-class attendance. (Some explanations will be given using the whiteboard which is not always picked up well by the cameras.) Experience with prior classes has shown that there is a strong correlation between attendance in class and overall course grades.

Feedback

If you have ideas to improve the course, you can send us anonymous feedback. Please note, however, that we cannot respond to you via the anonymous feedback form.

Assessment

• We will have two exams: a midterm exam and a final exam.
• There will be approximately 8 homeworks during the quarter.
• Course grades will be made from the weighted average of the exams and homeworks. The weights will be as follows: 40% for homework, 20% for the midterm, 40% for the final.

Late Policy

Life is complex; we understand. You are allowed to take four 24-hour extensions on homeworks, no questions asked (you may use at most one on each homework). After exhausting your four extensions, all future assignments turned in up to one day late will be graded with a 50% penalty. Assignments turned in after one day late are given automatic zeroes. Extenuating circumstances can be discussed with Prof. Nirkhe -- no TA for this course can approve additional extensions.

Collaboration

• You are allowed to collaborate on the homework to the extent of formulating your ideas as a group.
• You must write up the solutions to each problem set completely on your own and once your assignment is written up, you must not let others see your solutions.
• You cannot take pictures in the from the Office hours or copy any hints given.
• You must also list the names of everyone whom you discussed the problem set with.

Academic Integrity

• You are not allowed to search for solutions to problems on the internet or other sources outside of those given in class, the textbook, and the course website, or share your solutions through such means.
• You are not allowed to use ChatGPT or other LLMs.
• You are not allowed to post HW problems in Stack Overflow or MathOverflow.
• You are not allowed to use any theorems or results not proved in class.

---

Guidelines, Resources and Expectations

The following is consistent with the standards set at the University of Washington at large.

Academic Integrity

The University takes academic integrity very seriously. Behaving with integrity is part of our responsibility to our shared learning community. If you’re uncertain about if something is academic misconduct, ask me. I am willing to discuss questions you might have.

Acts of academic misconduct may include but are not limited to:

• Cheating (working collaboratively on quizzes/exams and discussion submissions, sharing answers, and previewing quizzes/exams)
• Plagiarism (representing the work of others as your own without giving appropriate credit to the original author(s))

Concerns about these or other behaviors prohibited by the Student Conduct Code will be referred for investigation and adjudication by (include information for specific campus office).

Students found to have engaged in academic misconduct may receive a zero on the assignment (or other possible outcome).

Conduct

The University of Washington Student Conduct Code (WAC 478-121) defines prohibited academic and behavioral conduct and describes how the University holds students accountable as they pursue their academic goals. Allegations of misconduct by students may be referred to the appropriate campus office for investigation and resolution. More information can be found online here.

Accessibility and Disability Resources

Your experience in this class is important to me. It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), please activate your accommodations via myDRS so we can discuss how they will be implemented in this course.

If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), contact DRS directly to set up an Access Plan. DRS facilitates the interactive process that establishes reasonable accommodations. Contact DRS at disability.uw.edu.

Religious Accomodations

Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy (https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/). Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form (https://registrar.washington.edu/students/religious-accommodations-request/).

Safety

Call SafeCampus at 206-685-7233 anytime – no matter where you work or study – to anonymously discuss safety and well-being concerns for yourself or others. SafeCampus’s team of caring professionals will provide individualized support, while discussing short- and long-term solutions and connecting you with additional resources when requested.

The University of Washington prohibits sex discrimination and sex-based harassment and expects all UW community members to respect one another in our shared academic and work environments. Sex discrimination and sex-based harassment can include sexual assault, relationship violence, stalking, unwanted sexual contact, sexual exploitation, sexual harassment, and discrimination based on sex.

Students who believe they have experienced sex discrimination or sex-based harassment are encouraged to contact a Title IX case manager by making a Title IX report. The case manager can provide guidance on available support resources and resolution options.