Homework completeness criteria

The syllabus states that the written homework is checked for completeness, but not correctness. This page explains in more detail what is meant by that. It does not mean "you can submit anything at all and you'll get credit". It does mean, "if your submission is evidence of a serious attempt to solve the problem, you'll get credit even if your solution is incorrect".

Here are more concrete examples of what is meant by that.

If a question requests a particular type of answer, a serious attempt will give the requested type of answer, even if the answer itself is not correct. For example, if the question states "give a regex or DFA deciding some language", and instead of giving a regex or DFA, the answer instead contains long run-on sentences talking about regular languages and using phrases from other parts of the course (for example, talking about the Pumping Lemma), but nowhere in the answer is something that looks like a regex or a DFA, that's not a serious attempt. If it asks to solve two counting problems (e.g., count the number of languages satisfying some constraint, and count the number of DFAs satisfying some constraint), but the solution appears to contain no statements about counting these objects (for example, "... since there are n^k ways to choose the DFA, and in this case n$=2 and k=8$, that gives 2⁸ = 256 ways to choose the DFA..."), that's not a serious attempt.

Or, for a problem like counting how many NFAs there are with n states and k symbols, just writing "n^k" clearly isn't sufficient (it's also not correct, but writing only the correct formula would also not be sufficient). Think back to any similar exercise we've done in lecture; it's very rare I will simply claim something is true without justifying why. When I do, I'll announce repeatedly that proving the claim is outside the scope of the course. Nearly every claim made is justified; your answers should also be justified. To what extent? Imagine one of your classmates says "I don't get it. Why is this true?" What would you say to convince them? That's the whole point of "proofs": to convince skeptical people that something is true.

So at the very least, try to understand what the question is asking for, and try to give an answer that really works. The point of the policy is that if your answer is of the right format and is clearly the sort of solution the question was asking for, but just doesn't work in all cases, then you shouldn't lose credit.

The idea is that by really actually trying hard to solve the problem, even if you fail, and only after failing do you see a correct solution, this is more beneficial than just being spoon-fed an answer before ever having thought seriously about the problem. The lectures are already full of spoon-fed examples, where you see the problem and then immediately see a solution. The purpose of the homework is to try (really try) to generate a solution yourself before seeing a solution.

Another reason for the policy is that since there are not points assigned to correctness, students should feel more free to discuss possible solutions on Piazza with each other. Of course, you shouldn't just post your solution, or copy someone else's solution. But explaining at a high level (without typing a detailed solution) how to solve the problem is a perfectly fine thing to do. If another student really gets what the question is asking for, and really gets a high-level explanation, and turns that into a concrete solution that they are able to write up on their own, then great!