We're sure you're aware of all of the following, and some of it is repetitious, but just to be sure we're all on the same page with respect to what homework solutions should look like:

**Always prove that your algorithm works.** Whether the problem specifically
asks for it or not, you should always prove that your algorithm works. This
will generally consist of two parts:

- Prove that your algorithm halts.
- Prove that it outputs the correct answer.

**Algorithm run times.** If an problem asks for an algorithm that
satisifies a run time bound (such as "the running time for your
algorithm should be O(m+n) for a graph with n nodes and m edges") you
must provide a justification that your algorithm satisfies the run
time bound.

**You may lose points for style.** Your proofs and explanations
should be clear, well-organized and as concise as possible. It is better to
err on the side of including too many details, however, you should not
belabor things that are completely obvious. Unfortunately, a lot of this is
subjective. Often, students think of proofs as merely either "right" or
"wrong". This would be true if they were expressed in every last detail in a
formal logic but not at the level that you will need to write them here.
Writing a proof is more like writing an essay. Along these lines, if you are
not able to find a complete answer to a problem, you are better off explaining
clearly what you've done rather than faking a proof.

Pictures and *short* pieces of pseudocode can be helpful, but they are
not sufficient. Make sure to label everything. Define all the variables you
use. Make sure you've explained everything clearly in English.

**Try rewriting your proofs.** Writing out your answer fully on a
piece of scratch paper before writing up the version to hand in really does
make a difference. You are more likely to catch mistakes or exceptions, and
your proof will be better organized.

**Set up good notation.** Many of the exercises in the book are phrased
almost entirely in English. It will be your job to rephrase them
mathematically when necessary. The first few lines of many of your proofs
will look something like, "Let *S* be the set of students taking
csep521." Make sure that you've clearly defined any variable you use. Choosing
good names for your variables is also important. For this class, it probably
won't matter too much, but for complicated proofs, it can make a big
difference.

**Collaboration** You are allowed to collaborate on the homework to
the extent of formulating your ideas as a group. However **you must write up
the solutions to each problem set completely on your own**. You must also list
the names of everyone whom you discussed the problem set with.