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 use them properly!
• 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.

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.

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.

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

  Analyze the running time

  • Unless otherwise noted, you will give the running time in big-O 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

  In general...
  • If you could put your pseudocode into a python interpreter, and it would pretty much compile, you're probably including too much detail.
  • If you ever use three or more words to refer to an object (like "the vertex we're processing now" or "the next vertex to come out of the queue") you probably want to make things more code-like (e.g. a variable name like curr or notation like next = queue.removeMin())
  • Code idioms, like loops, conditional branching, and especially recursion, should be phrased in code-like form, not English. Phrases like "repeat this process until..." or "...and so on" or "make a recursive call" are likely to be ambiguous in English and are much better written in code form.
  • Use good style in your pseudocode! Indent and/or use braces for nested structures, use meaningful variable names, you can even write comments!