Homework Style Guide

Algorithms

The phrase “describe an algorithm” always requires that you:

1. Describe the algorithm itself
2. Justify its correctness (with a full proof, unless otherwise specified)
3. Find a big-O description of its running time

Unless otherwise noted, you are allowed to use algorithms described in class (or prerequisite courses) as though you had library implementations of them. For example, you can say “run the BFS-based 2-coloring algorithm from class on the graph G” or “run the bipartite checking algorithm from lecture 5 on G” or “run Dijstra’s Algorithm with u as the source vertex.”

You may want to review the list of algorithms and data structures from 373

Since this is a course about efficient algorithms, we do deduct for algorithms that are slower than necessary, but (unless otherwise noted) we do not care about constant factors (i.e. we care about big-O efficiency). In general, an algorithm that is correct but (mildly) slower than optimal will get more points than an algorithm that is fundamentally incorrect, but fast.

Descriptions

In describing an algorithm, you need enough detail that the staff feels a student in class has enough detail to effectively implement it. In general, you may use a mix of English and pseudocode depending on what you feel is clearer. You may use phrases like “iterate through all vertices, marking them as unseen” instead of writing traditional pseudocode.

We do not care about details of how you format your input and output, as long as it’s clear to us what the output would be (unless otherwise stated in a problem). You can skip careful description of how data would be read-in or output. For example, if you are describing a shortest path algorithm, you can store the shortest paths in dist fields for every vertex, we’ll infer that’s where the answer is. But if we’re asking for a single number, you have to tell us which of the dist entries is the right one.

You may use any facts from class (by citing the lecture number and slide) or from 373 (citing just that you learned them there). There is no need to re-prove these facts.

Proofs

When writing a proof, your goal should be to convince another student in class of what you’re trying to prove.

When using proof by contradiction, remember to start with “Suppose, for the sake of contradiction, …” and the negation of what you’re trying to prove.

When using proof by induction, remember to clearly identify your Base Case, Inductive Hypothesis, and Inductive Step. We also recommend a sentence after your inductive proof to make sure it’s clear how the conclusion of the induction relates to the claim you’re trying to show (e.g. “since greedy is ahead through all i intervals, it is ahead at the end, and therfore its output is the maximum number of intervals”)

A good check after writing a proof is to ask “have I mentioned all the key steps of my algorithm somewhere in my proof” – if you haven’t, it’s a good indication you haven’t explained some aspect relating to that line.

Running Time

big-O/Theta/Omega bounds should be simplified and tight. An answer that is correct (but not tight) will usually receive a smaller deduction than one that is incorrect. You may assume you have access to standard library implementations of data structures when writing algorithms (e.g. say ``let D be a dictionary, implemented as a hash table’')

Programming Questions:

We will not grade your code on style, but we recommend following style and code structure guidelines from 373 (so you’ll be able to understand your code in a few months, and we can help you debug if we have time in office hours) We don’t usually have dedicated stress tests, but your code should still be efficient in big-O terms. Our tests do still have timeouts. While they are generous, you will still fail the test if your code is very inefficient.