General Information

Students are expected to be familiar with all of the information below. Please read it fully and carefully.

Instructor

Course Resources

1. Course website: https://cs.washington.edu/421

2. Gradescope, EdStem and other materials linked from the website above.

Quiz Section

CSE 421 has an associated quiz section on Thursdays this fall so that the course will be 4 credits; this also will be the norm in future quarters. Because this change is still working its way through the system, to get that 4th credit you will need to sign up for CSE 493Z also. Please do this if you haven't already done so. (It is technically optional but having the extra credit should be helpful to you. Signing up will not change your workload in the course. Your grade for CSE 493Z will be exactly the same as your grade in CSE 421.)

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-deisgn paradigms (including greedy algorithms, divide and conquer, dynamic programming, flow modeling, and others).
• Prove 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

There is a textbook associated with the course: "Algorithm Design" by Jon Kleinberg and Éva Tardos, Addison-Wesley, 2006. The International Edition is the same in paperback and there are other ways of accessing the textbook content if you only want online access to it.

This textbook gives a very good feel for how algorithm designers actually think about designing and analyzing algorithms. Each section is designed to be read sequentially rather than via random access to the content.

We will cover almost all of chapters 1-8 of the Kleinberg/Tardos text plus material from later chapters. In addition, we will borrow a small amount of material on divide and conquer algorithms from Introduction to Algorithms: A Creative Approach, by Udi Manber, Addison-Wesley 1989 and possibly other sources. We will make extra material available for this.

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.

FERPA

In addition to the above anonymous feedback, so we can ensure the security of your personal information, communication related to the course should be through EdStem or via your CSE or UW-issued email address. Personal email addresses should be avoided for course-related correspondence.

Assessment

We will have two exams: a midterm exam and a final exam.

The midterm exam will be in the evening on Wednesday, November 8 from 6:00-7:30 to avoid time pressure.

The final exam will be on Monday December 11th 2:30-4:20.

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: 55% for homework, 15-20% for the midterm, 25-30% for the final.

Homework Problem Types

There are two types of problems on homeworks: mechanical and long-form.

Mechanical problems usually ask you to execute an algorithm or give short answers, like an input that causes bad-behavior. These problems are usually shorter and require a surface-level understanding of what was discussed in lectures. There will be approximately one of these problems per homework, they will all be out 10 points.

Long-form problems generally involve designing an algorithm -- generally in by-hand (in pseudocode). Long-form problems also might ask you to consider real-world effects of using algorithms or to prove facts about algorithms. These problems usually require applying the contents of lectures to new scenarios. There will be approximately three of these problems per homework, they will all be out of 25 points.

Late Policy and Dropped problems

Instead of late days, we will count late problems submitted on homeworks; each problem will be its own gradescope submission box. You have a total of 10 late problem days over the course of the quarter. Only 2 of these late days may be used per problem. Submissions more than 48 hours late, and late submissions after you have used your ten late problem days will receive 50% credit provided that they have been submitted prior to our publishing homework solutions.

Late submissions are intended to handle the "normal" difficulties during a quarter (midterms in another class, family birthday party to attend, bad colds). If you have a more extreme situation (e.g., an extended illness or a family emergency) contact Paul (via email or Ed post) for accommodations.

Additionally, we will drop some of your lowest scores when calculating your homework score. We will count your 7 highest mechanical problems, and your highest 20 long-form problems (that means we will likely drop about 1 mechanical problem, and about 3 long-form problems, but the exact number dropped will vary depending on the exact length of homeworks). Dropped problems can be thought of as part of the late policy, but they are also intended to reflect that algorithms problems sometimes require a specific insight that even someone with a solid understanding might occasionally miss.

Late problem days will be greedily applied to the first late problems submitted late during the quarter (even if these problems end up being dropped).

Academic Integrity

The goal of our exercises is for you to fully understand and internalize the approach to the materials. To that end, we take academic integrity very 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; any such problem will not be dropped when we calculate homework grades; this is not a substitute for reporting violations of the policies.

Collaboration

You are allowed (and encouraged!) to discuss homework problems with other students. With algorithms problems, it's very common to need one or two key insights that are much easier to discover talking out loud with others. But, to make sure you are learning the content while collaborating, we require that you:

• Do not take away any notes or screenshots from your discussion.
• Take a 30-minute break¹ before writing up your solution individually.
• Cite the names of all of your collaborators somewhere in your writeup.

Programming problems must also be written up individually. That means you may discuss plans with others (e.g., which data structures you plan to use) and you may help each other debug, but you may not write code while looking at another student's code, nor may you type anything on another students' code. If you are confused as to whether or not some collaboration is allowed, ask us! No set of rules will be completely exhaustive. If something weird happens, please tell us too! We will not penalize you if you tell us what happened before turning in the assignment. We will not consider it an academic integrity violation if you inform us what happened before you submit.

Resources Outside of CSE 421

You are strongly encouraged to seek out general resources beyond official course resources (other textbooks, lecture notes, etc.) --- very often it takes two or three different explanations for a concept to click, so finding different explanations is a good thing -- with the following caveats:

• Definitions and terminology can differ significantly (and subtly!) depending on the author. Be careful that other resources are saying what you think they are saying.
• You may not search with the intent of finding a solution to a specific homework problem (see below).
• You may not use commercial tutoring resources like Chegg for the problems we ask, nor post our materials or your answers to those websites.
• You may not publicly post code you have written for this course (nor your solutions to written assignments), even after the course is over.

Our homework problems

While you are permitted to seek out general resources, you may not search intending to find answers to the problems we ask you on homeworks. We choose and design problems for their pedagogical value; the number of pedagogically-valuable problems is limited for some of our topics, so similar problems are likely to appear elsewhere.

• You may not use a written solution for an equivalent problem as a resource, but you may use a written solution for different problems on the same topic (e.g. other divide and conquer proofs are a fine resource).
• You may not post our problems on the internet (e.g. on Chegg, Reddit, or other sites).
• You may not use a language model (like Chat-GPT), as it is probably drawing on solutions for equivalent problems in its training set, incorrect, or both.

Scenarios

What happened?	Is it a violation?
When searching for general information, you accidentally find the exact question we asked. You tell the staff, and provide a link to what you found.	Not a violation! We’ll say “thanks for letting us know!” and make sure you didn't plagiarize. There won’t be a penalty but only a warm, fuzzy feeling.
You and a friend separately write up solutions, then compare. Your friend suggests that your conclusion is a little unclear. You formulate a new conclusion on a Zoom call together.	Violation! That is no longer your individual writeup.
You and a friend separately write up solutions, then compare. Your friend suggests that your algorithm runs in time O(m+n) not O(m^2). You wait 30 minutes, then return to your writeup, decide your friend was right, and update your writeup.	Not a violation! Bug fixes and minor rewordings done by you at another's suggestion are fine. The writeup is still substantially yours.
You find a textbook with sample solutions. You see that they like to introduce variables with “Consider” and use “hence” instead of “because.” You copy these words, because they seem cooler.	Not a violation! Single words or stock phrases are things you can learn from. It is not a violation to emulate style (but "hence" is a little archaic).

Course Tools

Ed

Ed is our discussion board and the right place to ask any questions about the course. We will happily answer questions from lecture or about general concepts. We also will answer clarifications about homework (e.g. correcting typos). You are most encouraged to answer each other’s questions on the message board as well. If you have a question that might reveal your approach to a homework problem, you must ask the question privately. For accommodations and other private questions, you can ask privately on Ed or email the instructor directly. Only you and the course staff can see a private question on Ed.

Gradescope

Gradescope is the tool to turn in completed assignments. After grading, you can also find our feedback there and submit regrade requests if needed. You will get an automatic email with account setup instructions before HW1 is due.

Canvas

We will use Canvas for Panopto lecture recording and release of solutions. We will not communicate through Canvas -- please monitor this website and Ed instead.

Accommodations

If you have, or think you may have, a temporary health condition or permanent disability, contact Disability Resources for Students (DRS) to get started with accommodations. Accommodations for faith or conscience reasons must be requested within the first two weeks using the Registrar’s request form. The UW’s religious accommodations policy is available here. Your performance in this course should not be affected by circumstances beyond your control. We can still work with you for situations other than the university-wide accommodations. If anything does come up, you should contact the course staff as early as you can.

What happens if I get sick?

If you are sick, stay home. Don't come to class or quiz section even if it is an exam. If it is for an exam, please contact us as soon as possible to let us know and we can arrange an alternative time for you to take the exam.

---

---

---

---

^{1. In the era when Paul was a student, instructors recommended watching a half-hour episode of Gilligan’s Island for that break. This rule became known as The Gilligan’s Island Rule but Gilligan’s Island isn’t on typical streaming services - it was old and on re-runs even then but the number of equivalent alternatives has only grown. [go back]}