The course staff must critically examine close to ten thousand
pages of homework submissions this semester! We desperately need your help
to make sure homeworks are graded and returned quickly. If you have any
questions or concerns about these policies, please don't hesitate to ask in
lecture, during office hours, or on Piazza.
I apologize in advance for the length of this document. Most of this
stuff is obvious to almost everybody, but after teaching this class for
many years, I've seen a lot of strange things.
Homework Logistics: How to submit
- All homework solutions must be submitted electronically via
Gradescope.
Please enroll yourself on Gradescope using the
entry code M6722X.
Submit one PDF file for each numbered homework
problem. Gradescope will not accept other file formats such as plain
text, HTML, LaTeX source, or Microsoft Word (.doc or .docx).
- You can register with Gradescope using any name and email address
you like. If you are using an alias or a non-university email address
on Gradescope, please
fill in this form to tell us who you are
so we can give you credit for your homework. If
you are not logging into Gradescope with your real name or university
email address, do not include your real name or your university email
address in your homework solutions.
- Homework solutions may be submitted by groups of at most
three students. We strongly encourage (but will not
require) every student to work in a group with at least one other
student. Students are are responsible for forming their own homework
groups. Groups may be different for each numbered homework
problem.
- For group solutions, exactly one member
of each group submits the solution to each problem. Even
if the groups are identical, the submitter may be
different for each numbered homework problem.
- Whoever submits any group solution must also submit the
names of the other group members via Gradescope. Gradescope will
then automatically apply the grade for that submission to all
group members. If this information is not entered correctly, the
other group members' grades will be delayed or possibly
lost entirely.
- If you discover that your name was omitted from a group
homework submission, please submit a regrade request.
- As error correction, each submitted homework solution should
include the following information at the top
of the first page:
- Your GradeScope name
- Your Gradescope email address
- The problem number (of the form "X.Y")
For group solutions,
include the Gradescope name and email address of every group
member. If you are typesetting your solutions with LaTeX, please use
our solution template (see pdf).
- We will not accept late homework for
any reason. To offset this rather draconian policy, we will count
only the homework problems you actually submit toward your final course
grade. Specifically:
- If you submit more than
27 24 homework problems, only your
highest 27 24 problem scores count. (If you submit everything, this
this is equivalent to dropping almost two three complete homework
sets.)
- If you submit fewer than
27 24 homework problems, your exams
will have (slightly) larger weight in the final grade
calculation. Clarification (4/17): when we say "(slightly)", we do mean slightly: the exams may be worth a total of 72%+x and HWs a total of 28%-x, for some 1% <= x <= 2% the exact value of which is up to the discretion of the instructors.
- You must submit at least half the homework to pass the
class.
- Update (3/26): due to the COVID-19 situation, we have decided to relax the policy and count your highest 24 problem scores instead of 27.
We may forgive coursework under
extreme circumstances, such as documented illness or injury.
Forgiving homework requires a serious long-term issue that prevents
submission of multiple homework sets; the regular homework
policies already allow missing a few submissions without serious
penalty. “Extreme circumstances” for exams do not include
travel for job interviews. We will compute your final course
grade as if your forgiven work simply do not exist; your other work
will have more weight. Please ask the instructor for details.
Please make it easy for the graders to figure out what you mean in the
short time they have to grade your solution. If your solutions are difficult to
read or understand, you will lose points.
Be Honest
- Write everything in your own words, and properly
cite every outside source you use. We strongly encourge
you to use any outside source at your disposal, provided you use your
sources properly and give them proper credit. If you get an idea from an
outside source, citing that source will not lower your grade. Failing to
properly cite an outside source—thereby taking credit for ideas that are not
your own—is plagiarism.
The only sources that you are not required to cite
are the official course materials (lectures, lecture notes, homework and exam
solutions from this semester) and sources for prerequisite material
(which we assume you already know by heart).
- List everyone you worked with on each homework problem.
Again, we strongly encourage you to work together, but you must give everyone
proper credit. If you work in a group of 20 students, then all 20 names
should appear on your homework solution. If someone was particularly helpful,
describe their contribution. Be generous; if you're not sure whether someone
should be included in your list of collaborators, include them. For
discussions in class, in section, or in office hours, where collecting names
is impractical, it's okay to write something like "discussions in class".
- Please see our
academic integrity policy for more details.
Be Clear
- Write legibly. If we can't read your solution, we can't give
you credit for it. If you have sloppy handwriting, use LaTeX.
Please don't submit your first draft. Writing legibly also helps you
think more clearly.
- We strongly recommend typesetting your homework
using LaTeX. (In
particular, we recommend TeXShop
for Mac OS X, TeX Live for Linux
(already included in most distributions), and MiKTeX
for Windows.) We provide a LaTeX template for homework solutions.
- You are welcome to submit scans of hand-written homework
solutions, but please write clearly using a black pen on plain white unlined
paper, and please use a high-quality scanning
app (or an actual high-quality scanner). We recommend
printing your scanned document to check for readability before
submitting.
- Write sensibly. You will lose points for poor spelling,
grammar, punctuation, arithmetic, algebra, logic, and so on. This rule is
especially important for students whose first language is not
English. Writing sensibly also helps you think sensibly.
- Write carefully. We can only grade what you actually
write, not what you mean. We will not attempt to read your mind. If your
answer is ambiguous, the graders are explicitly isntructed to choose an
interpretation that makes it wrong. Writing carefully also helps you
think carefully.
- Avoid the Three Deadly Sins:
- Write complete solutions, not just examples. Don't describe
algorithms by showing the first two or three iterations and then writing
"and so on". Similarly, don't try to prove something by demonstrating it
for a few small examples and then writing “do the same thing for all $n$”.
Any solution that includes phrases like “and so on”, “etc.”, “do this for
all $n$”, or “repeat this process” may get a score of
zero. Those phrases indicate precisely where you should have
used iteration, recursion, or induction but didn’t.
- Declare all your variables. Whenever you use a
new variable or non-standard symbol for the first time, you must specify
both its type and its meaning, in English. Similarly,
when you describe any algorithm, you must first describe in English
precisely what the algorithm is supposed to do (not just how it works). Any
solution that contains undeclared variables may get a score of
zero, unless it is otherwise perfect. This rule is especially
important for dynamic programming problems.
- Short complete answers are better than longer
answers. Unnecessarily long answers (which by definition are
not perfect) may get a score of zero. See below.
- State your assumptions. If a problem statement is
ambiguous, explicitly state any additional assumptions that
your solution requires. (Please also ask for clarification in
class, in office hours, or on Piazza!) For example,
if the performance of your algorithm depends on how the
input is represented, tell us exactly what representation you
require.
- Don't submit code. Describe your algorithms using
clean, human-readable pseudocode. Your description should allow a bright
student in CS 225 to easily implement your algorithm in
their favorite language.
- Don't submit your first draft. Revise, revise,
revise. After you figure out the solution, then think about the right way to
present it, and only then start writing what you plan to submit.
Yes, even on exams; do your initial scratch work on the back of the page.
"I Don't Know"
- For any homework problem or subproblem (except for bonus questions), you can write IDK ("I Don't
Know") and get 25% of the points for that problem or subproblem. You would get
the points if and only if IDK is the only content of your
answer. Any answer containing "IDK" anywhere and any
additional text would immediately get a zero.
Note, however, that readable, correct, but suboptimal solutions are always worth more than 25%. Reasonable progress toward a correct solution will receive partial credit, which could easily exceed 25%.
Be Concise
- Keep it short. Every homework problem can be answered
completely in at most two typeset pages or five handwritten pages;
most problems require considerably less. Yes, I am aware of the crushing
irony.
- Omit irrelevant details. Don't write "red-black tree" when you mean
"balanced binary tree" or "dictionary". Don't submit code; we want to see
your ideas, not syntactic sugar. If your solution requires more than two
typeset pages, you are providing too many irrelevant details.
- Don't regurgitate. Don't explain binary search; just
write "binary search". Don't write the pseudocode for Dijkstra's
algorithm; just write "Dijkstra's algorithm". If the solution
appears on page 6 of Jeff's notes, just write "See page 6 of Jeff's
notes." If your answer is similar to something we've seen in
class, just say so and (carefully!) describe your changes. You will
lose points for vomiting.
- Automatic zero: We will give an automatic zero to
answers which we consider to be too long, unclear, and
repetitious. We will also do it if we can not follow the logic of
your answer. We might even do it without reading them. If you
do not know the answer then use IDK—don't waste your
time and don't waste our time.
Content: What to write
- Answer the right question. No matter how clear and polished your
solution is, it's worthless if it doesn't answer the question we asked. Make
sure you understand the question before you start thinking about how to answer
it. If something is unclear, ask for clarification! This is especially
important on exams.
- Justify your answers. You must provide a brief justification for
your solutions, as evidence that you understand why they are correct.
Unless we explicitly say otherwise, we generally do not want a
complete proof of correctness—because complete proofs would be too long,
tedious, and unenlightening—but rather a high-level sketch of the major steps
in the proof. Proofs/justifications are only required on exams if we
specifically ask for them.
- By default, if a homework or exam problem asks you to describe
an algorithm, you need to do several things to get full credit:
- If necessary, formally restate the problem in terms of
combinatorial objects such as sets, sequences, lists, graphs, or trees. In
other words, tell us what the problem is really asking for. This
is often the hardest part of designing an algorithm.
- Give a concise pseudocode description of your algorithm. Don't
regurgitate, and don't turn in code!
- Describe a correct algorithm.
- Justify the correctness of your algorithm. You usually won't
have to do this on exams.
- Analyze your algorithm's running time. This may be as simple as
saying "There are two nested loops from 1 to n, so the running time
is O(n˛)." Or it may require setting up and solving a recurrence, in
which case you'll also have to justify your solution.
- Describe the fastest correct algorithm you can, even if the
problem does not include the words "fast" or "efficient". Faster algorithms
are worth more points; brute force is usually not worth much. We will not
always tell you what time bound to shoot for; that's part of what you're
trying to learn. However, if your algorithm is incorrect, you won't get
any points, no matter how fast it is!
Some problems may deviate from these default requirements. For example, we
may ask you for an algorithm that uses a particular approach, even though
another approach may be more efficient. (Answer the right question!)
Web page adapted from those of previous semesters.