Instructor: Chinmay Nirkhe (OH: Mondays 4:30pm - 6:00pm, Wednesday 4:30pm - 5:30pm in CSE2 353)
Head TAs: Jay Dharmadhikari, Timothy Tran
Course Staff: Click here
Location: Gates 20
Times: M, W, F 3:30 - 4:20 pm
Recitation section: see time table
Midterm: May 5th 3:30 - 4:20
Final: June 12th 2:30 - 4:20
EdStem: Link
Gradescope: Link

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.

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!

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. Both books are highly suggested but are not mandatory. I have had both on my bookshelf for a decade and they have brought me an immeasurable amount of value.

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.

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.

• We will have two exams: a midterm exam and a final exam. In person attendance is expected for both exams. We cannot entertain requests for early finals even for internships. If an internship is insisting on starting on a date that overlaps with the UW quarter, that is a red flag for the internship demonstrating their disinterest in your education. I would warn you to avoid such a position.
• 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 approximately as follows: 40% for homework, 20% for the midterm, 40% for the final.

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 25% penalty, two days late will be graded with a 50% penalty. Assignments turned in after two days late are given automatic zeroes. Extenuating circumstances can be discussed with Prof. Nirkhe -- no TA for this course can approve additional extensions.

• 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.

• 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.

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

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).

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.

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.

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/).

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.