# Homework FAQ

When I have to write an algorithm, how should I format my answer?

Traditionally, we have a 4-part algorithm format: main idea, pseudocode, proof of correctness, and running time analysis. See this instruct.pdf for a very detailed explanation. Recently, however, we have started allowing students the option of writing either a main idea OR pseudocode – whichever describes your algorithm best. We will do our best to specify what we expect you to write in each question, but when in doubt, default to a “3-part” solution, which is discussed here.

How efficient does my algorithm need to be?

Do your best. We may or may not give a running time requirement up-front (sometimes that would give a strong hint on how to do the problem). Some baseline considerations: Most problems have a natural naive/brute-force algorithm (e.g. “try all possibilities”) or other trivial approaches (e.g. “apply [suboptimal known algorithm] without any modification or thought”). These usually receive no credit. Exponential-time algorithms usually get no credit. We often award partial credit to algorithms that are slower than our official solutions.

Can I cite theorems and algorithms from the textbook or lecture without proof?

Yes.

Can I use theorems and algorithms from other sources?

As detailed in the syllabus, you should not look up problem solutions using the internet/other sources. If you do run into a useful theorem/algorithm that aids in your solution, (a) you must prove it in your solution and (b) make sure to cite the source you got it from.

Is my interpretation of the problem correct? What about such-and-such case?

Piazza is not a good forum to figure out what a problem is asking / ask for hints or confirmation. Even something as innocuous as, “So on x input we would return y solution, correct?” can reveal a lot about a problem, which hurts other students’ understanding. Please first try asking fellow students and coming to office hours. If after doing this you still believe the problem is poorly worded and genuinely ambiguous, please go ahead and explain the ambiguity, but we will tend to avoid answering such questions when the problem is not unclear. Much of the challenge of the problem sets is precisely understanding the nuances of the problem, and asking to be given all the details defeats that purpose.

Do we give our algorithm’s worst-case running time, or average running time?

Most algorithms in this course are deterministic ones, for which we are always concerned with the worst case. For randomized algorithms, the expected running time is acceptable. Note that this may receive less credit if a superior deterministic algorithm is known.

Do I have to give Θ(⋅) running times for my algorithms, or only O(⋅)?

If it is possible to provide a $\Theta(\cdot)$ bound in a simple manner, then you should do so. If it is not, then give the tightest $\mathcal{O}$ bound possible.

What’s the deal with Θ(⋅) vs O(⋅) notation anyways?

We try to stick with the actual definitions, which means to use $\Theta(\cdot)$ notation when you’re describing the exact asymptotic runtime. However, the textbook often uses $\mathcal{O}(\cdot)$ notation even when giving tight bounds; if in the above example you wrote $\mathcal{O}(n)$ for the runtime, we would still give you full credit because the runtime was correct, even though it’s better practice to use $\Theta(\cdot)$ notation.

Can I make reasonable assumptions about the computational model?

Yes. If you think the assumption is not totally obvious, feel free to explain it as you perform the runtime analysis (eg “Because indexing into arrays takes constant time, …”)

Can I make [some additional assumption] about [some homework problem] that was not given in the problem?

No. For example, don’t assume numbers in a list are distinct, don’t assume a graph is connected, etc.

Do I need to provide a justification for my answer?

Yes, unless the problem explicitly states that justification is not required.

How rigorous does my explanation need to be?

Rigorous enough for any average CS170 student to understand it completely.

Can I use things shown in discussion/lecture/textbook without proof?

General response to this is: you are free to use things shown to you in lecture/textbook/discussion without proof, within bounds. The “within bounds” means that be reasonable with us — if we ask you to show that $\sum_{k=1}^n k = \Theta(n^2)$, don’t say “This was shown in discussion so it is true.” Don’t take away the heart of a problem and claim it was done in X, that’s being too clever for your own good and won’t fare well. We expect students to be able to reason about what “within bounds” means. So feel free within bounds. And if in doubt about anything — ask.