Instructor: Chinmay Nirkhe (OH: Wed 2:30 - 4:00pm in CSE2 217)
Head TA: Toby Thornburg
Location: Gates 20
Times: M, W, F 1:30 - 2:20 pm
Midterm: Feb 2nd 12:30 - 2:20
Final: Mar 16th 2:30 - 4:20
EdStem: Link
Gradescope: Link

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.

Prerequisites: CSE 312; CSE 332, MATH 208 or MATH 340.

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.

• Course grades will be made from the weighted average of the exams and problem sets. The weights will be: 56% general questions, 4% challenge questions, 15% midterm, and 25% for the final.
• There will be 9 problem sets during the quarter.
• The problem sets consists of 3 general questions and 1 challenge question.
• Except set 4 consists of 1 general question and 1 challenge question.
• There are 25 general questions. We will drop the score of your bottom 3 general questions.
• There are 9 challenge questions. We will drop the score of your bottom 2 challenge question.
• We will have two exams: a midterm exam and a final exams, each 2 hours. In person attendance is expected for both exams.

Life is complex; we understand. You are allowed to take a 24-hour extension on any 15 problems (general or challenge) throughout this course. You can take an extension on any number of problems in a given set. 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 must also list the names of everyone whom you discussed the problem set with. If you made use of generative AI, you must cite this and how you used the AI tool.

The primary goal of problem sets is to help you learn and solidify the course material. Working through problems is one of the best ways to develop intuition, strengthen problem-solving skills, and prepare for the exams — which constitutes a significant fraction of your grade. Problem sets count for a fraction of your grade and are used primarily for cementing concepts, challenging your understanding, guiding your learning, and ensuring steady practice.

You are encouraged to collaborate with your peers on problem sets. Discussing approaches, explaining your reasoning, and hearing how others think about the problems are excellent ways to deepen your understanding. However, ltimately, you are responsible for engaging with the coursework in the way that helps you learn most effectively.

The use of generative AI other than the course approved GPT is prohibited. This includes for studying or learning/clarifying concepts. This is because other generative AI do not have the contextuality of the course and will likely not align with the primary objective: your learning. The course approved GPT has been designed with the contextuality of this course in mind and will assist you better. Still it is not a replacement for in-person interaction with the instructor or TAs.

You are allowed to use the course approved GPT only after having both (a) worked on the problem for at least one hour by yourself and (b) have met with the instructor or TA of the course for assistance on the problem and have sufficiently ruminated on their assistance. Use of the course approved GPT for reformulating concepts is encouraged but we caution moderation. Reliance on generative AI can be detrimental to your long-term learning. However, we leave the decision of how to use generative AI effectively for concept learning up to you.

If an AI system or a peer significantly helps you in your problem-solving process, you should acknowledge them in your submission (e.g., by listing their name or the tool you used on that problem). This is both because it is an academic norm, and also to help us understand how the class is doing; although it will have no effect on the grading.

Lastly, the exams will not allow any access to AI tools but will be open to notes or resources you have generated using AI tools prior to the exam.

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.