CS 6363.005.19S — Writing Policies and Advice for Homework and Exams
This page contains general policies and advice regarding writing of homework and exam solutions.
The most important thing to keep in mind is to be nice to the grader,
whether it is Kyle or the TA.
If your solutions are difficult to read, we 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…
- 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!
- Use 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 CLRS, just write, "see page 256 of CLRS."
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.
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!
This is especially important on exams.
Most homework and exam 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, and this will be especially true when
we start playing with graphs.
- 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.
The QE itself requires proofs of correctness for every problem, although we may relax that
requirements for class exams due to time constraints.
- 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 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.
We may sometimes deviate from these default requirements.
For example, if we ask you to use a specific technique, then you must use that technique to get
credit.
Answer the right question!
Finally, here are some bad writing and thinking habits that come up often in algorithms 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\).
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\).