Homework Guidelines

Most homework questions ask you to give an algorithm to solve a particular problem. Some other problems instead ask you to prove particular properties of a given algorithm, or provide a counterexample to some claim, etc. When your answer to a question involves “giving an algorithm”, unless otherwise specified, a complete solution to that question consists of the following three things:

• a description of an algorithm to solve the problem;
• a claim of the algorithm's correctness, and a proof of that claim; and
• a statement of the algorithm's complexity (in time and, if requested, space), and a proof of that claim.

Your solution is evaluated according to the following criteria:

Correctness

Your algorithm must produce the correct output for all valid inputs, as specified by the problem statement, and it must also satisfy all specified time or space complexity requirements. In addition, the statements that you offer as proof of the algorithm's correctness and of its complexity must themselves be correct; that is, they must actually prove what you claim about the algorithm.

Style

The presentation of your solutions should professional and direct. Imagine that you're directing your write-ups toward an outsider who's knowledgeable about algorithms but isn't in our class, maybe a CS professor at another college. The environment of our classroom and the style of the problem sets are generally pretty light-hearted, but please keep a professional demeanor in your write-ups.

Clarity

Your solution should be easy to understand for a person familiar with the subject matter of the course, but not the details of the problem you are solving. Your notation should be straightforward, and your prose should guide the reader clearly through the reasoning of your solution.

Precision

Your solution should be unambiguous to a reasonable and well-informed, but nevertheless skeptical, reader.

Conciseness

You should avoid unnecessary exposition and detail as much as possible. Use mathematical syntax or pseudocode in place of repetitive or long-winded prose. Do not describe the thought process that led you to a solution; instead, simply state your solution. It is also usually unnecessary to provide examples when explaining your algorithm; if an example seems necessary, consider redesigning the logic of your algorithm to make it easier to follow.

Every solution you hand in must be typeset in LaTeX and exported to PDF. Please read through my LaTeX resources page for help getting started with LaTeX. On that page, I have posted an example .tex document that meets all the formatting criteria outlined below; you're welcome to use it to get started creating your own documents.

Your submission must be on letter-size (8.5" x 11") paper — note that many LaTeX installs use A4-size paper by default, which is not appropriate for submissions. There should be an effective margin of one inch on the left and right sides of the main body of your submission. It's okay for hanging section labels to run into this margin if you desire. There should also be a margin of approximately one inch at the top and bottom of your text. Headers and footers may fall within this margin or may start an inch away from the page edge.

Every submission must have a header with exactly these contents:

The header must be separated from the body of your submission by a horizontal line. The problem-set number (X) is between 1 and 10; each problem set is made up of up to three problems. The problem number (Y) is specified in the assignment; it corresponds to the order in which the problems are described, regardless of the order in which you turn them in. A “list_of_usernames” is either the string “no one” or a comma-separated list of usernames. If you talk to me, another faculty member, a student outside our class, or someone else, they still count; please credit them in your collaborator list. (Though it's okay to go over two collaborators in this case.)

Your typesetting must use text styling (fonts, spacing, alignment, etc.) to differentiate prose, mathematical variables, and pseudocode. Check Google or Wikibooks for pseudocode typesetting advice. Do not use especially small or large fonts; the default sizing used by the LaTeX “article” package is appropriate, except for its humongous section headings. Again, my example document fixes the section headings so they're reasonable for homework.

If you'd like to include a diagram, a hand-drawn one is acceptable; scan it or take a nice-quality photo and insert it into your document. Diagrams are almost never necessary in your submissions, though; the one exception is when your answer consists of an example that is easiest to convey by drawing it.

Submit your solution to each problem as a PDF in the hand-in directory on your Courses network drive, with the following filename: username-X.Y.pdf, where X is the problem-set number and Y is the problem number. Note that's a hyphen and not an underscore.

The writing that you do for these problem may take the form of prose, pseudocode, or math, and often all three are required for a high-quality submission.

Pseudocode's main purpose is to support the precision and conciseness requirements of your solution. Pseudocode doesn't necessarily have to look much like regular computer code; sometimes it can be as simple as English prose with meaningful indentation. But avoid being long-winded when writing this way: a good general guideline is that no line of pseudocode should be as long as the width of your page. (And usually they should be much shorter!)

If you do write pseudocode, and it contains a lot of variables or sophisticated logic, provide a short prose explanation first. Talk about the big picture of your solution, describe the meaning of the important variables, and state any invariants that your algorithm maintains as it runs. (Note that this does not mean that you should describe the exact mechanics of your code in prose. Just describe the big picture; the prose should not be redundant with the pseudocode.)

I recommend that you explicitly divide the presentation of your solution into the three sections described in the "Contents" section above. Here's a template that serves people well:

You may assume that your inputs are always valid (that is, that they conform to the specification given for the problem), but you must not assume they are non-degenerate unless specified. Be careful about edge cases.

If you are given input and told that it has a specific property (that it is sorted, say, or that it is a spanning tree of a given graph), you do not have any guarantees about the process used to construct the input. Assuming that a particular process was used to construct it is an invalid line of reasoning. You should consider your inputs as handed down by an omniscient oracle.

By default, all indexing is assumed to be 1-based; that is, an array A of length N has entries A[1], A[2], and so on up to its last entry, A[N]. (Same goes with strings, multi-dimensional arrays, lists of nodes in a graph, etc.) Really, you should always specify your indexing, but if you don't, I'm going to assume it's 1-based, and consider A[0] to be an out-of-bounds array access.

A[n] refers to the element at index n of array A. In contrast, A[1...n] refers to all values in A at indices from 1 up to n. We use the latter notation for declaring a length-n array, and also for implicitly specifying that n is the length of an array provided as an argument to a function.

Any result that we prove in class, or that we just state without proof in class, is fair game for use without proof in homework turned in after that result is covered (or on an exam, for that matter). For example, you can just say to use mergesort in your algorithm, and then state in your running-time analysis that “mergesort takes O(n log n) time”, without any further proof being necessary. Same goes for properties of algorithms that we prove or offer without proof; for example, “the Gale–Shapley algorithm returns a stable matching of its inputs” is a valid statement as part of a proof you write.

However, this is the only valid way to invoke material from class. Here are some common invalid approaches:

• It is not sufficient to only refer to proofs we do in class. For example, “X is true for the same reason that Y [which we covered in class] is true” is not a valid proof of X.
• A similarity between your algorithm and one we covered in class is not sufficient evidence that it has similar properties. For example, “my algorithm X is similar to algorithm Y [which we covered in class]; since Y has property Z, X also has property Z” is flawed reasoning.

This means that if you modify the inner workings of a “textbook” algorithm, your proof of correctness (or running time) for this new algorithm must start from scratch, even if it is nearly identical to the proof of correctness (or running time) of the original algorithm. (An often preferable strategy, described below, is to modify the inputs to your algorithm so they can be operated on by the textbook algorithm.)

A note on tone: we're operating under a sort of creative fiction — our objective is to report a correct solution, not describe our thought process in designing it. You may feel a little uncertain about your work, but the style to aim for is concrete statements.

This means that you should use an active, constructive voice in describing your solution, rather than a passive or tentative one. Many people (and I am often one of them) tend to write things like “we could construct a graph to solve the problem. The graph would have such-and-so properties...”. Instead, it is preferable to just write: “construct a graph by following these steps...”.

One last suggestion: be lazy! A common algorithmic technique is to transform a given problem into an instance of a familiar problem, use a known algorithm to solve this auxiliary problem, and then transform the output into a solution for the given problem. This approach has three great benefits over rolling your own complete algorithm: it's often far easier to describe, for your reader to understand, and to prove correct. However, sometimes searching too hard for a lazy solution might take you down the path to an incorrect solution; carefully scrutinize your solution and try to find inputs that make it produce incorrect results.