This page contains general policies and advice regarding writing of homework solutions.

- Write concise, legible, and correct solutions. You will lose points for bad handwriting, spelling, grammar, arithmetic, algebra, logic, etc. If we cannot tell what you meant to write, you will receive no credit. Along those lines…
- Strongly consider typesetting your homework solutions. We highly recommend learning LaTeX to create visually pleasing and easily readable solutions. A template for homework solutions can be found here (and will be updated specifically for this course when we release the first homework). Microsoft Word, Apple Pages, or another modern word processor might also work if you really need a WYSIWYG editor, but please use their built-in equation editors.
- We can only grade what you write, not what you mean. If your answer is ambiguous, we will assume you are wrong.
- Don't submit your first draft. Figure out the solution, think about how to present it, and only then start writing. Revision is easier if you're writing on a computer!
- Consider using pseudocode or outline format to describe algorithm details, but do not turn in source code. It can be useful to give the main idea in English, but an algorithm written entirely in English prose is hard to follow. On the other hand, raw syntax meant for a compiler is also hard to follow. Use the text for examples of the right balance. Ideally, your description should allow a component programmer who has not taken the course but does have access to the material to implement the algorithm in their favorite programming language.
- Make the punch line obvious when you can. If there is a single expression or value to report, then circle or highlight it to make it easier to find. In general, you should always do this when reporting running times.
- Omit irrelevant details. Don't write "red-black tree" when you mean "balanced binary search tree" or "ordered dictionary". Don't write "depth-first search" when you mean "whatever-first search". Don't explain binary search or write the pseudocode for an algorithm I give in lecture; just write "binary search" or "use that algorithm". If the solution appears on page 256 of 3Marks, just write, "see page 256 of 3Marks." If your solution requires more than two typeset pages, you are providing too much detail.
- Include relevant details. If the problem statement is ambiguous, explicitly state any additional assumptions your solution requires. Better yet, email us to ask for clarification, and do so at least a few days before the deadline so we have time to respond. If your running time depends on how the algorithm's input is represented, tell us how it should be represented. If you require a specific base case to solve a recurrence, tell us what that base case is.
- Don't babble. Don't simply write nonsense while dropping a few key words. You'll get little, if any, partial credit.

Often homework problems will ask you to describe an algorithm. You need to do several things to get full credit:

- If necessary, formally restate the problem in terms in combinatorial objects like sets, lists, graphs, trees, etc. In other words, tell us what the problem is really asking for. Often, this is the hardest part of designing an algorithm.
- Give a concise pseudocode explanation of your algorithm. You may consider giving a very brief high level English overview as well. Again, though, don't give real programming code, as that is too hard for the grader to parse.
- Describe a correct algorithm. Don't babble!
- Justify the correctness of your algorithm. You must provide a justification for why your algorithm is correct, usually as a mathematical proof. If you made a recursive call, why does the use of your recursive solution aid in building the whole thing? If you reduced to a graph problem, why does the solution to that graph problem give the right output for your algorithm? Restating your algorithm pseudocode in English is not the same thing as justifying its correctness. The goal here is to convince us that you understand why your algorithm is correct.
- Analyze your algorithm's running time and space usage. This may be as simple as saying "There are two nested for loops from \(1\) to \(n\), so the running time is \(O(n^2)\)," or (unlikely in this course) it may require setting up and solving a recurrence. In the latter case, you'll need to justify the solution to your recurrence.
- Describe the fastest correct algorithm you can. Faster algorithms are worth more points, and brute force is usually not worth much. We may not always tell you what time bound to aim for, because that is part of what you're trying to learn. Fully correct and justified slow algorithms are generally worth more than fast algorithms that are nevertheless incorrect.

- Write general solutions, not examples. Don't describe an algorithm by showing the first two or three iterations and then writing "and so on". Don't try to prove something by demonstrating it on a few small examples and saying "now do this for all \(n\)". You cannot rely on us to find the pattern in what you're doing, and phrases like "and so on", "etc.", "do this for all \(n\)", or "repeat this process" may indicate that you don't see the pattern either. Those phrases indicate you should have used iteration, recursion, or induction, but you didn't.
- Declare your variables. When you use a new variable or non-standard symbol for the first time, specify both its type and its meaning in English. When you describe an algorithm or recurrence, explicitly state the meaning of its input parameters, what the output of your algorithm/recurrence is, and how that output depends upon the parameters. This latter point is especially important if your algorithm needs some additional parameters that were not part of the original problem.
- Never use weak induction.
Always, always, ALWAYS use a strong inductive hypothesis ("the algorithm is correct for inputs
of size \(k < n\)"), even in proofs that apply the inductive hypothesis at \(n-1\).
Why would you ever want to tie \(n-2\) hands behind your back?

Perhaps more importantly, never try to prove something "for \(n+1\)" by assuming it works for \(n\). Now you're doing weak induction and you're tempted to build a special case of the next problem size up instead of proving something for the general case. I don't care if you have a template that says otherwise; start at \(n\) and assume truth for all values less than \(n\).