CS 473: Homework Policies

The course staff must critically examine several thousand pages of homework submissions this semester! We desperately need your help to make sure homeworks are graded and returned quickly. If you have any questions or concerns about these policies, please don't hesitate to ask in lecture, during office hours, or on Piazza.

• What homework is for
• No late homework
• Don't plagiarize!
• Deadly Sins
• “I don't know” is not a thing.

• Logistics: How to submit
• Form: How to write
• Content: What to write

I apologize in advance for the length of this document. Most of this stuff is obvious to almost everybody, but after teaching algorithms for a couple of decades, I've seen a lot of strange things.

What homework is for

The homework is your opportunity to practice doing the thing. The lectures and textbook and office hours hopefully provide good intuition and motivation and justification for the skills we want you to develop, but the best way to develop those skills is by trying to solve the problems yourself. The practice is far more important than the solution.

Because the homework is intended to help you develop new skills, you are likely to get stuck; for some problems, you may have no idea how to even start. And that's okay. That's why we have a textbook and lecture videos and office hours and Piazza and a library and Wikipedia; helping you get unstuck is part of our job. That's why we encourage students to work together; not so that you can share solutions, but so that you can share ideas and suggestions and feedback.

Similarly, you won't necessarily develop a complete solution to every homework problem yourself, and you may not be able to tell which parts of your final submitted solution are correct. And that's also okay. That's why we provide homework solutions—not just to show you the answer, but to help you see your own work more clearly. That's why we grade your homework submissions—not to give you points, but to give you feedback to help you improve.

To get the most out of any particular homework problem, it's important not just to aim for a solution to that specific problem, but to pay attention to how you're solving it. Every problem is an opportunity to practice that kind of problem; every solution is an example of that kind of solution.

It's also important to aim for improvement—not perfection (which is impossible), not being better than other people (which can be toxic), but doing the thing better than you did yesterday, every day.

In practice, course grades in CS 473 are determined almost entirely by exams, which ask you to demonstrate the same skills that the homework is meant to develop; homework scores have minimal impact. So even if your goal is to optimize your course grade, practicing with the homework problems is more important than getting the right answers.

No Late Homework. Ever.

• We will not accept late homework for any reason. The deadline is the deadline.
• Gradescope automatically stops accepting submissions at the deadline (Wednesday at 9pm). You can replace your submission as often as you like before the deadline; only your last submission before the deadline will actually be graded. We strongly recommend submitting something well before the deadline, to avoid any last-second emergencies.
• To offset this rather draconian lateness policy, we have adopted a liberal policy of dropping low homework scores when calculating final grades.
• We may forgive homework under extreme circumstances that prevent the submission of a significant fraction of the homework, such as a documented disability, illness, injury, or other emergency. We will compute your final course grade as if your forgiven homework simply do not exist; your other work will have more weight. Students requiring accommodation for a disability should first contact DRES. Please ask Jeff for further details.

Deadly Sins

• Write general solutions, not examples. Don't describe algorithms by showing the first two or three iterations and then writing “and so on”. Similarly, don't try to prove something by demonstrating it for a few small examples and then writing “do the same thing for all n”. Any solution that includes phrases like “and so on”, “etc.”, “do this for all n”, or “repeat this process” automatically gets a score of zero. Those phrases indicate precisely where you should have used iteration, recursion, or induction but didn’t.
• Explain what you're doing. Whenever you introduce a new abstract object, you must explain in English what it means. When you describe a graph, you must specify in English the purpose/meaning of each vertex and edge. Whenever you describe an algorithm, you must specify in English precisely what problem your algorithm is trying to solve. Whenever you give a recurrence, you must describe in English precisely what function the recurrence is supposed to compute.
  • In particular, when you describe a function/algorithm with input parameters, you must explicitly describe the meaning of those parameters and exactly how the output of your function/algorithm depends on them.
  • We are not asking you to separately explain your algorithm line by line in English; rather, we want a complete specification of the problem that your algorithm is solving. Describe how to use your algorithm, not just how it works.
  • If the problem statement already includes a complete specification of your algorithm, you do not need to repeat it. On the other hand, if your algorithm uses additional input parameters or solves a more general problem than the one we ask for, then the problem statement does not include a complete specification of your algorithm.
• Never use weak induction. Always, always, ALWAYS use a strong induction hypothesis, even in proofs that only apply the induction hypothesis at n−1. Why would you even want to tie n−2 hands behind your back? Imperfect proofs that use weak induction hypotheses will be more heavily penalized, especially if the induction argument has the form P(n)⇒P(n+1) instead of P(n−1)⇒P(n). Basically, weak induction should die in a dumpster fire.
• Don't cheat. You must write everything in your own words, and properly cite every outside source you use, including other students. Using ideas from other sources or people is normal and expected, but using ideas from other sources or people without citation is plagiarism. Copying other sources verbatim, even with proper citation, is plagiarism. Don't do that.

Logistics: How to submit

• All written homework solutions must be submitted electronically via Gradescope. Submit one PDF file for each numbered homework problem. Gradescope will not accept other file formats such as plain text, HTML, LaTeX source, or Microsoft Word (.doc or .docx).
• Homework solutions may be submitted by groups of at most three students. We strongly encourage (but will not require) every student to work in a group with at least one other student. Students are responsible for forming their own homework groups. Groups may be different for each numbered homework problem.
  • Exactly one member of each group submits the solution to each problem. Even if the groups are identical, the submitter may be different for each numbered homework problem.
  • Whoever submits any group solution also tells Gradescope the names of the other group members. Gradescope automatically applies the grade for each submission to all group members. If this information is not entered correctly, the other group members' grades will be delayed or possibly lost entirely. Gradescope automatically limits groups to at most three students.
  • If you discover that another member of your group was omitted from a homework submission, please submit a regrade request.
• As error correction, each submitted homework solution should include the following information in large friendly letters at the top of the first page.
  • The homework number
  • The problem number
  • The name and NetID of every group member.
  If you are typesetting your solutions with LaTeX, you are welcome to use our solution template.

Form: How to write

Please make it easy for the graders to figure out what you mean in the short time they have to grade your solution. If your solutions are difficult to read or understand, you will lose points.

Be Honest

• Write everything in your own words, and properly cite every outside source you use. We strongly encourage you to use any outside source at your disposal, provided you use your sources properly and give them proper credit. If you get an idea from an outside source, citing that source will not lower your grade. Failing to properly cite an outside source—thereby taking credit for ideas that are not your own—is plagiarism.

  The only sources that you are not required to cite are the official course materials (lectures, lecture notes, homework solutions, and exam solutions from this semester) and sources for prerequisite material (which we assume you already know by heart).

• List everyone you worked with on each homework problem. Again, we strongly encourage you to work together, but you must give everyone proper credit. If you work in a group of 20 students, then all 20 names should appear on your homework solution. If someone was particularly helpful, describe their contribution. Be generous; if you're not sure whether someone should be included in your list of collaborators, include them. For discussions in class, in labs, in office hours, or in other large groups, where collecting names is impractical, it's okay to write something like "discussions in class" or "Tuesday evening Grainger study group".
• Please see our academic integrity policy for more details.

Be Clear

• Write legibly. You will lose points if the graders find your work difficult to read. Writing legibly also helps you think more clearly.
  • We strongly recommend typesetting your homework, especially if you have sloppy handwriting. We recommend using LaTeX, but you are welcome to use whatever program and/or markup language you like. We will provide a LaTeX template for homework solutions.
  • You are welcome to submit scans of hand-written homework solutions, provided they are clear and easy to read. We strongly recommend writing with a black ink on white unlined paper, using a scanning app instead of a raw photo, and printing your scanned document to check for readability before submitting. Please do not submit your first draft.
  • The graders have complete discretion to decide whether a submission is difficult to read. In borderline cases, the graders will first give a warning, asking the student for specific improvements in future homework submissions, rather than immediately deducting points. Please take this feedback seriously.
• Write sensibly. You will lose points for poor spelling, grammar, punctuation, arithmetic, algebra, logic, and so on. This rule is especially important for students whose first language is not English.
• Write carefully. We can only grade what you actually write, not what you mean. We will not attempt to read your mind. If your answer is ambiguous, the graders are explicitly instructed to choose an interpretation that makes it wrong.
• Don't submit your first draft. Revise, revise, revise. First figure out the solution, then think about the right way to present it, and only then start writing what you plan to submit. See also "write legibly".
• State your assumptions. If a problem statement is ambiguous, explicitly state any additional assumptions that your solution requires. (Please also ask for clarification in class, in office hours, or on Piazza!) For example, if the performance of your algorithm depends on how the input is represented, tell us exactly what representation you require. Yes, even if the assumption is “obvious”.
• Don't submit code. Describe your algorithms using clean, human-readable pseudocode. Your description should allow a bright student in CS 225 to easily implement your algorithm in their favorite language, using a software library containing implementations of every algorithm we’ve seen in class, without knowing what problem you're trying to solve.

Be Concise

• Keep it short. Every homework problem can be answered completely in at most two typeset pages or five handwritten pages; most problems require considerably less. Yes, I am aware of the crushing irony.
• Omit irrelevant details. Don't write "red-black tree" when you mean "balanced binary tree" or "dictionary". Don't write "depth-first search" when you mean "whatever-first search". Don't submit code; we want to see your ideas, not syntactic sugar. If your solution requires more than two typeset pages, you are providing too many irrelevant details.
• Don't regurgitate. Don't explain binary search; just write "binary search". Don't write the pseudocode for Dijkstra's algorithm; just write "Dijkstra's algorithm". If the solution appears on page 374 of Jeff's book, just write "See page 374 of the textbook." If your answer is similar to something we've seen in class, just say so and (carefully!) describe your changes. You will lose points for vomiting, especially if you get the details wrong.
• Don't bullshit. You will not get partial credit for word salad that happens to include some correct keywords.

Content: What to write

• Answer the right question. No matter how clear and polished your solution is, it's worthless if it doesn't answer the question we asked. Make sure you understand the question before you start thinking about how to answer it. If something is unclear, ask for clarification! This is especially important on exams.
• By default, if a homework or exam problem asks you to describe an algorithm, you need to do several things to get full credit:
  • Describe the problem that your algorithm is supposed to solve. This is often the hardest part of designing an algorithm. See the second Deadly Sin.
  • Give a concise pseudocode description of your algorithm. Don't regurgitate, and don't turn in code!
  • Describe a correct algorithm.
  • Justify the correctness of your algorithm. You must provide a brief justification for your solutions, as evidence that you understand why they are correct. Unless we explicitly say otherwise, we generally do not want a complete proof of correctness—because complete proofs would be too long, tedious, and unenlightening—but rather a high-level sketch of the major steps in the proof. Correctness arguments are required on exams only when we specifically ask for them.
  • Analyze your algorithm's running time. This may be as simple as saying "There are two nested loops from 1 to n, so the running time is O(n²)." Or it may require setting up and solving a recurrence, in which case you'll also have to justify your solution.
  • Describe the fastest correct algorithm you can, even if the problem does not include the words "fast" or "efficient". Faster algorithms are worth more points; brute force is usually not worth much. We will not always tell you what time bound to shoot for; that's part of what you're trying to learn. However, if your algorithm is incorrect, you won't get any points, no matter how fast it is!
  Some problems may deviate from these default requirements. For example, we may ask you for an algorithm that uses a particular approach, even though another approach may be more efficient. (Answer the right question!)

No “I don't know” credit

I used to offer 25% partial credit for answering any problem with "I don't know". After doing this for 20 years, I was finally convinced to end this practice in Spring 2020. The 25% partial credit was intended to reward self-awareness; I still believe that truthfully admitting ignorance indicates more mastery of the material than submitting a completely incorrect answer.

However, in practice, the IDK partial credit undermined students' confidence, and it introduced a distracting element of gamesmanship. Students who lacked confidence in their own mastery often submitted IDK rather than risking a score under 25%, even when they could produce solutions worth more than 25%. Other students spent far too much mental energy trying to guess whether their partial solution was worth more or less than IDK; I heard several complaints that the IDK policy discouraged students from "trying" or "guessing". At least for these students, IDK credit shifted the focus of homework and exam questions toward risk-avoidance or grade optimization, and away from the actual course material.

Especailly during the late 2010s, I saw struggling students increasingly use IDKs in a way that was clearly self-destructive, such as answering IDK to a majority of the final exam questions, meeting the minimum homrwork requirement by submitting 16 IDKs, or ignoring the fact that submitting IDK for any homework problem is actually worse that submitting nothing at all (unless you're already failing for other reasons).

In particular, there is some evidence that the IDK policy unfairly impacted female and underrepresented minority students.

So no more partial credit for "I don't know". We want you to make a good-faith effort to solve every problem, especially on exams.

(While I'd love to report that this policy change had a positive effect on stress and exam grades, COVID makes comparisons with earlier semesters difficult to impossible.)