Syllabus

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

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!

The Pandemic Reality

While the general course of the pandemic has improved, We are still feeling effects of the pandemic. We intend to stick to this syllabus as closely as possible, we may propose changes if there are significant changes to the public health situation. If we do make changes, it will always be to your benefit. In return, we ask that you do not suffer in silence. If unforeseen circumstances arise during the quarter, you should let us know. The sooner we are made aware, the more options we will have for designing accommodations.

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.

The midterm exam will be given in the evening of Monday February 13th. We will schedule an alternate exam time for students who cannot make the main exam due to work or other immovable conflicts.

The final exam will be given on Monday March 13th at 2:30.

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 -- either by-hand (in pseudocode) or in actual (Java) code. 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 may submit up to 6 problems late over the course of the quarter, each of which can be submitted up to 48 hours late. Submissions more than 48 hours late, and late submissions after you have used your six late problems will receive 50% credit.

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 Robbie (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 problems will be greedily applied to the first 6 problems submitted late during the quarter (even if these problems end up being dropped).

Lecture Activities

In lecture, we will ask you to respond to polling questions. These activities are not graded -- they help you catch common misconceptions, and help me adjust how fast I'm going during lecture, but do not affect your grade.

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.

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

Zoom

While we hope to run the course primarily in-person, some office hours will be held online. If we have a synchronous lecture as part of our contingency plans, we will use zoom. Zoom meetings will be restricted to accounts logged in with @uw.edu email addresses. If you have trouble joining a meeting, make sure you choose the "Sign in with SSO" option.

Ed

Ed is our discussion board and the right place to ask any questions about the course. It works like Piazza, but Piazza is moving to an ad-supported model, so we paid for an alternative. 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 only use Canvas for gradebook syncing (at the end of the quarter). We will not communicate through Canvas -- please monitor this website and Ed instead.

Java

Homeworks occasionally contain a small programming portion. Because this course assumes knowledge from CSE 332, these programming questions are given in Java. If you do not already have Java from prior quarters, you can grab it from AdoptOpenJDK. We expect any JDK above 8 would work.

Accommodations

If you have, or think you may have, a temporary health condition or permanent disability, contact 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.

Contingency Plans

What happens if I get sick?

Remember to follow the university policies (which include rules on reporting positive tests if you've been on campus, restrictions on when you can return to campus, and some times when masking may be required for you, even if not for everyone).

Additional accommodations (e.g. extra late problems, extra dropped problems) may be possible if you have an extended illness. Contact Robbie if you're sick.

We will be recording lectures and posting to panopto so you can keep up/catch back up when you're healthy. Sections will not be recorded, but the handouts and solutions will be available.

What if I get sick right before an exam?

Don't come to the exam if you're sick! Contact Robbie once you know you're too sick to attend, and we'll schedule a makeup exam for when you're ready to return to campus.

If your illness hits for the final, we may utilize other options like remote exams or temporarily giving an incomplete until you're well enough to return and take the exam. We will work with you to decide which accommodation is appropriate to your illness.

What if I'm not sick, but won't be comfortable in a large lecture hall?

Lectures will be recorded; we won't track in-person attendance.

We expect exams to take place in person. We will have a number of empty seats in the exam room, but we may not be "every other seat."

We will have some accommodations available for people with significant reasons to not attend the main exam (e.g., the conflict exam for illnesses), but these will be limited.

If you have a health condition (mental or physical) that means you should not be in a large lecture hall, you should contact DRS (see Accomodations above) to investigate accommodations.

What happens if a staff member gets sick?

Depending on who is sick (and how sick they are) we may find a substitute or convert an in-person meeting to zoom. In extreme circumstances, we may cancel a section or office hour, but we do not expect that to be common. Any such changes will be announced via Ed.

If Robbie has an extended illness, we may switch to zoom lectures for a short time.

^{1. Some CSE instructors have previously recommended watching an episode of Gilligan’s Island for that break, and this rule is therefore known as The Gilligan’s Island Rule but Gilligan’s Island isn’t on Netflix. Robbie recommends Parks and Rec. [go back]}