Homework Guidelines

Formatting Homework

You can write your homework in one of the following ways:

  1. Typeset your answers using LaTeX. We strongly recommend doing this. See the Latex Guide for help using LaTeX.
  2. Type your answers using a mainstream word processor.
  3. Neatly handwrite, then use a flatbed scanner or smartphone app (such as CamScanner) to produce a PDF. Do not simply take a photo and dump it into a PDF.

The readers work hard to grade your homeworks in a timely manner, and with useful feedback. Given the size of the course, we require a certain format of all homeworks: each problem must start on a new page, and clearly display the problem number; if a problem has multiple parts, make sure that each part fits on a page. You must also select the pages for each problem when you submit to Gradescope, if you do not do this, you may not get points on that problem.

List your collaborators on the first page of your submission. If you have no collaborators, you must explicitly write “none”.

Algorithmic Design Solution Format

Algorithmic design questions require an algorithm description, justification, and runtime analysis, unless specific otherwise. The algorithm description could be presented in pseudocode, or a description in English. We will grade based on the correctness of your approach and the clarity of your explanation, not on code-level details or syntax.

  1. Algorithm description. This can be presented in pseudocode, or a description in English. We will grade based on the correctness of your approach and the clarity of your explanation, not on code-level details or syntax.
    • Your pseudocode does not need to be executable. You should use notation such as “add X to set S” or “for each edge in graph G”. Remember you are writing your pseudocode to be read by a human, not a computer.
    • See DPV for examples of pseudocode.
  2. Justification. This will usually be in the form of the main idea, expressible in a couple of sentences, in the style of DPV. The justification should be convincing — it should convey that you have a clear picture of why the algorithm produces the correct answer on an arbitrary input. This justification does not need to be a formal proof — we will specifically ask for a proof of correctness when needed.
  3. Runtime analysis. You should use big-O notation for your algorithm’s runtime, and justify this runtime with a runtime analysis. This may involve a recurrence relation, or simply counting the complexity and number of operations your algorithm performs.

Solo Problems

Some problems on the homework may be labelled as solo problems. These problems are written to be easier than “standard” homework problems, where you are not allowed to collaborate with other students on these problems or use any LLMs for help. You may still consult staff for any clarifying questions. The goal of these problems is to give yourself a benchmark for how well you would do if a similar problem appeared on an exam. Therefore, these questions will be graded on completion only, not the correctness of your solution. A staff member will then provide detailed feedback on your solution during grading.