Unless otherwise specified, solutions will be turned in electronically via this Catalyst dropbox.
Homework turned in must be PDF or text.
For most homeworks, you will need to submit your assignment in two separate files. Please be careful about following the specific instructions. (This is being done, because different TAs will grade different parts of the homework.)
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:
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. Some of the exercises will be 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 cse417." 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.
Don't prove things we already know. If you are using a fact that is in the book or was in one of the videos, you can simply state it without proof.
Collaboration Collaboration on any canvas quiz (whether part of homework or an actual quiz) is strictly prohibited. You are allowed to collaborate on the other parts of 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.
Be careful. Homework problems have been carefully chosen for their pedagogical value and hence might be similar or identical to those given out in past offerings of this course at UW, or similar courses at other schools. Using any pre-existing solutions from these sources, or any source not explicitly linked to or discussed on our course web page constitutes a violation of the academic integrity expected of you and is strictly prohibited.