The course staff must critically examine over ten 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.
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.
We will not accept late homework for any reason.
Gradescope automatically stops accepting submissions at the deadline (Tuesday at 8pm). 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 accomodation for a disability should first contact DRES. Please ask Jeff for further details.
“I don't know”
- Answering “I don't know” (and nothing else) to any required problem or sub-problem, on any homework or exam, is worth 25% partical credit. (No “I don’t know” credit for extra-credit problems, sorry!)
- Empty or missing submissions are not the same as “I don’t know”. Synonyms like “No idea” or “What is this I don't even” or “Je ne sais pas” or “分かりません” or “
¯\_(ツ)_/¯” or “🤷♂️” are acceptable substitutes, but you must write something.
- Readable, correct, but suboptimal solutions are always worth more than 25%. Reasonable progress toward a correct solution will receive partial credit, which could easily exceed 25%.
- If you answer “I don't know” on homework, you will get zero feedback on your progress toward a solution for that problem, which is the entire point of the homework. Also, our flexible homework policy implies that submitting “I don't know” for a numbered homework problem is almost certainly worse for your overall course grade than skipping that homework problem entirely.
- If you find yourself wanting to answer “I don’t know” frequently, something is wrong. Ask for help!
We've identified a small number of bad writing (and thinking) habits that are strongly correlated with poor performance in algorithms courses, but are easy to avoid. Homework and exam solutions that commit any of these sins will receive an automatic zero. Yes, we really mean it. We’re not trying to be scary or petty (Honest!), but we do want to break a few common bad habits that seriously impede mastery of the course material.
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.
Declare your variables. Whenever you use a new variable or non-standard symbol for the first time, you must specify both its type and its meaning, in English. When you describe a DFA or NFA, you must specify the purpose of each state in English. Whenever you describe an algorithm, you must specify in English prceisly 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. Any solution that contains undeclared variables automatically gets a score of zero.
In particular, when you describe an algorithm/recurrence with input parameters, you must explicitly describe the meaning of those parameters and exactly how the output of your algorithm/recurrence depends on them.
We are not asking for an additional English explanation of your algorithm, but a compelte specification of the problem 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? Any proof that uses a weak induction hypothesis automatically gets a score of zero, unless it is otherwise perfect. Basically, weak induction should die in a fire.
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 without citation is plagiarism. Copying other sources verbatim, even with proper citation, is plagiarism. Don't do that.
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.
- Write everything in your own words, and properly cite every outside source you use. We strongly encourge 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, or in office hours, where collecting names is impractical, it's okay to write something like "discussions in class".
Please see our academic integrity policy for more details.
If we can't read your solution, we can't give you credit for it. We strongly recommend typesetting your homework using LaTeX. You are welcome to submit scans of hand-written homework solutions, but please make sure they are clear and easy to read. If you have sloppy handwriting, use LaTeX.
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.
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.
- 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.
- 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 "Disjktra's algorithm". If the solution appears on page 6 of Jeff's notes, just write "See page 6 of Jeff's notes." 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. If you don't know the answer, just say so.
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:
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!)
- Describe the precise problem that your algorithm is supposed to solve. This is often the hardest part of designing an algorithm. See the first 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!