Writing Policies and Advice

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

Form: How to Write

The most important thing to keep in mind is to be nice to the grader. If your solutions are difficult to read, they will be far less lenient with mistakes. If they are impossible to read, you will receive no credit.

• 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…
• Consider typesetting your homework solutions. We highly recommend learning LaTeX to create visually pleasing and easily readable solutions. A template for homework solutions will be made available shortly after release of the first homework assignment. 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. Incidentally, you can write equations in those editors using… LaTeX!
• 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 initial thoughts. 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 an outline format to describe algorithm details, but do not turn in computer source code. It can be useful to give the main idea in English, but an algorithm written entirely in English prose is often hard to follow. On the other hand, raw syntax meant for a compiler can be almost as hard to follow for us puny humans. Ideally, your description should allow a competent 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, highlight, or bold it to make it easier to find. In general, you should always do this when reporting running times.
• Omit irrelevant details. If your solution requires more time to write than to solve, you are probably writing too much. (For official solutions, Emily tends to be a bit of a hypocrite with this last point, but she likes to think the extra detail helps you understand her thought process.)
• Include relevant details. If the problem statement is ambiguous, explicitly state any additional assumptions your solution requires. Better yet, email Emily to ask for clarification, and do so at least a few days before the deadline so she has time to respond and pass the knowledge on to others. If your running time depends on how the algorithm's input is represented, tell him how it should be represented. If you require a specific base case to solve a recurrence, tell him 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. And you'll make Emily a little, if not a lot, grumpier.

Content: What to Write

The most important thing here is to answer the right question. No matter how good your solution is, it is useless if you answer a question we didn't ask. If the question is unclear, ask for clarification!

Often, homework problems will ask you to describe an algorithm. For CS 6363, you will need to include the following 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 the grader what the problem is really asking for. Sometimes, especially when graphs are involved, 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 an informal 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 the grader that your algorithm is correct.
• Analyze your algorithm's running time. 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 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 checking all possible solutions 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.

We may sometimes deviate from these default requirements or may break them down into individual problem parts. Answer the right question!

Bad Habits

Finally, here are some bad writing and thinking habits that come up often in algorithms and other discrete math courses. Doing one of the things in this list is often a huge red flag that either you aren't explaining things correctly (so we can't grade what you know) or worse, that you aren't thinking of things correctly. We reserve the right to severely dock your score if you break any of the following rules.

• 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\). The first statement includes the second as a special case. Using the second statement directly is like tying \(n - 2\) hands behind your back.

Along the same lines, resist the temptation to prove something "for \(n + 1\)" using the assumption that it's true 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 realize you may have been given a template that says otherwise, but think of it this way: Induction is really just a fancy setup for direct proofs, and it would be odd to start a proof with "consider an arbitrary object of size \(n + 1\)." So instead, you should take your arbitrary object of size \(n\), assume your statement is true about objects of any size \(k < n\), and finish your argument about the original object of size \(n\).