Style Guide

Expectations for proofs

In general, proofs in 421 are not graded nearly as strictly as you are used to in 311. In 311, we need to make sure we know that you know what you're doing. Now that you're in a 400-level course, we believe you know what the starting point of a proof should be, so you'll often be allowed to skip those pieces.

Here are some things we really cared about in 311 that we don't care about in 421.

• When doing a direct proof of an implication, you do not need to re-introduce variables if you use the same names as the problem statement.
  • This rule also means we can often omit explicitly calling arbitrary variables arbitrary. Though we still need to properly treat them as arbitrary!
• When doing a proof by induction, you do not need to explicitly define a predicate P()
• If the type of a variable (e.g. "integer" or "character") is clear from context, it does not need to be mentioned when introduced (though it still needs to be mentioned if it appears in the justification of a future step)
• Statements we made you prove in 311 can sometimes be taken as "obvious"
  • For example, the sum of two even numbers being even can just be asserted, it does not need a proof in this class.
  • If in doubt, ask us what we expect to be proven.

On the other hand, some things we do still care about:

• Non-direct proofs (e.g., proof by contradiction, contrapositive, or induction) need to be introduced as such at the start of the proof
• In an induction proof, you must say "by IH" (or an equivalent) when using your inductive hypothesis.

What does it mean to "describe an algorithm"

If we ask you to "describe" or "design" an algorithm (or use any similar phrase), then you need to do four things.

1. Give us some intuition

Many of our problems have 1-2 core ideas in them. Telling us what you're intending to do (just in 1-2 sentences) makes it much easier for us to understand your code. You're not proving your code correct here, nor describing details. You're just giving 1-2 sentences of what you want to do.

2. Tell us what the computer should do

• Unless otherwise noted, we want pseudocode.
• You are permitted to use these algorithms and data structures from 332 as though you had a library for them, unless a problem says otherwise.

3. Tell us why it is correct

• We need a careful proof of correctness.
• Your target audience is someone who has come to lecture and section, but hasn't done the problem yet. That means you can use facts from class, but you should assume that your reader hasn't thought about the details of the problem.

4. Analyze the running time

• Unless otherwise noted, you will give the running time in worst-case, big-Theta terms. You may need to introduce variable names if they are not given in the problem.
• A 2-3 sentence justification is usually sufficient (often by giving a quick justification for the running time of the various sections of code).

Pseudocode

We have some advice and examples in this pdf. See also the the tex file that generated the pdf.

Length

Your goal should be to write a solution that is fully correct, but also fully clear. A solution that spends excessive space on agreed-upon basics may obscure the key ideas. We thus limit the length of your submissions. Unless otherwise noted:

• The staff solution (more-or-less) fits in one typeset page.
• Your solution should fit into two typeset pages (or three handwritten pages). If your solution draft appears much longer than that, we encourage you to visit office hours to talk to a staff member about what information you're spending too much space on.
• Staff reserve the right to "stop grading" at the end of the limits in the above (though we usually give a warning before enforcing the policy).