Staple your entire solution once in the upper left
corner. Do not use paper clips, tape, glue, spit, or rubber bands. Do not try
to keep pages together by folding or tearing.
Homeworks that do not follow these formatting requirements
will automatically
receive a grade of zero. This is not a joke.
For oral homeworks, each group will schedule a presentation
time with the professor. Watch the course webpage for announcements
regarding this process.
Each member in a group will present at least one
problem from a given homework set. The assignment of who presents what
will be done
randomly at the beginning of the presentation session.
Please be nice to the grader! Make it easy for me to see
what you're doing. If your answers are hard to read, I'll be MUCH
less sympathetic to your mistakes. All this goes for exam
problems, too.
-
Write concise, legible, and correct solutions. You
will lose points for bad handwriting, spelling, grammar,
arithmetic, algebra, logic, and so on. If we can't decipher what you
wrote, you will get no credit. This is especially important for
students whose first language is not English. If your handwriting is
bad, it's time to learn LaTeX. (1337-5p33k = teh 5uxx0r!!)
- Use pseudocode or outline format to describe your algorithms. Do
not turn in source code! Too much syntactic sugar distracts the
reader (and the writer!)
from what's the algorithm is really doing. On the other hand, raw English prose
is also usually
insufficient. See the textbooks and lecture notes for examples of the type of
presentation we want.
Ideally, your description should allow a competent programmer who has not
taken this course to
easily implement your algorithm in their favorite programming language.
-
Make the punch line obvious. Emphasize your final answers by putting a box
around them, or using a
highlighter, or some similar trick.
- Omit irrelevant details. Don't turn in the piece of paper you used to
figure out your answer;
copy the relevant information onto a new empty page. If the same algorithm works
equally fast whether
the input is an array, a singly linked list, a doubly linked list, or a binary
tree, try to describe it
so that a competent programmer can easily use any of these abstract data types.
- Include relevant details. If a problem statement is ambiguous,
explicitly state any additional
assumptions that your solution requires. (Of course, you should also ask for
clarification in class, in
office hours, or on via email.) For example, if the performance of
your algorithm depends on
how the input is represented, tell us exactly what representation you require.
If your solution to a
recurrence assumes a particular base case, tell us what base case you require.
- Don't regurgitate! If your answer is a simple modification of
something we've seen in class,
just say so and (carefully!) describe the changes. If the complete and correct
answer is on page 263 of
the recommended tetbook, the best solution you can submit is "See page
263 of the textbook."
Period. Same with the lectures, the lecture notes, and previous exams or
homeworks from the current
semester.
However, if you find a solution from any other source, such as a web page,
a journal paper, a
different algorithms textbook, an official homework solution from some earlier
semester, or your mom, you must rewrite the solution in your own words, and you must
properly cite your
sources. Assume the grader will have access to all the official course
material, but nothing else.
While we strongly encourge you to use any outside source at your
disposal, please remember that
the homework is supposed to demonstrate that you understand of the material, not
just how to use Google and a printer.
- Don't babble! If you don't know the answer, don't do a brain dump,
hoping to get partial
credit for incuding a few key words. That will never work in this class. Part
of what you're supposed
to learn here is how to tell when you don't know the answer. Answering "I don't know" (and nothing else) to
any homework or exam
question is automatically worth 25% partial credit for that
question. If you try to fake it, you'll get nothing. Remember,
though, that a course average of 50% or less is an automatic F.
Convince the grader that you understand exactly what you're doing.
- Answer the right question. Duh. No matter how clear and
polished your solution is, it's worth absolutely nothing 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!
- Justify all your answers. Unless the problem specifically says
otherwise, every homework and
exam problem requires a proof. Without a proof, even a perfectly correct answer
is worth
nothing. In particular, the sentence "It's obvious!" is not a
proof; many 'obvious' things are actually false!
-
By default, if a homework or exam problem asks you to give/show/describe/develop
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, lists, graphs, trees, etc. In
other words, tell us what the problem is really asking for.
This is often the hardest part of designing an algorithm!
- Describe the most efficient algorithm possible. The more
efficient your algorithm, the more points you get. Brute force is
usually not worth very much. We will not always tell you what time
bound to shoot for; that's part of what you need to learn!
- Give a concise pseudocode description of your algorithm.
But don't regurgitate! And don't turn in source code!
- Justify the correctness of your algorithm. You usually
won't have to do this on exams.
- Analyze your algorithm's running time and space usage.
This may be as simple as saying "There are two nested loops from 1 to
n, so the running time is O(n2)." On the
other hand, it may require setting up and solving a summation and/or a
recurrence, in which case you'll also have to prove your answer is
correct.
Some problems may deviate from these default requirements. For example, you may
be asked for an
algorithm that uses a parrticular approach, even though another approach may be
more efficient. (See the
first point in this section.) Exam problems will rarely ask for proofs of
correctness.
-
Don't make the reader extrapolate. It is never enough to explain what
happens during the first one
or two iterations of an algorithm, and then say "and so on". If we can't
immediately tell just by
looking what happens during the 17th, 42nd, or 31337th iteration, your
description is incomplete. Algorithms or proofs that use phrases like
"and so on", "etc.",
"repeat this for all X", and "..." will get no credit. Those are
perfect indications that
your algorithm should have used a loop or recursion, or that your proof should
have used induction, but
didn't.
The audience here will be considered "experts", since I'll obviously be familiar
with the background
material and the problem at hand. So you don't need to explain big O notation or
any other background
from the class, and you don't need to provide motivation. (After all, your
motivation is probably that
I assigned it!)
- Aim to present your solutions in 5 minutes. This is probably a bit
ambitious, especially during
the first weeks. However, I will stop you after 10 minutes on one
problem, so you should
practice giving your solution quickly and accurately!
Ideally, you will want to write out your solution, even if you don't need to turn
it in. Very often you will only find a bug in the solution when trying to write
it down, and even if it
is correct, you will improve your presentation by first writing out the argument
to clarify it in your own mind.
- The "I don't know" policy also works for oral homeworks. If you have
no idea of a solution,
then you might as well say "I don't know" and nothing else to the TAs,
because they will give
you a 0 if your solution is completely wrong.
- Don't dwell on the details! Assume that the listener, who is after
all the instructor for the class, is
familiar with the topics from class. If the solution only differs from something
presented it class by a
small detail, say that! For example, if the problem is dealing with minimum
spanning trees, saying "The
algorithm is identical to Kruskal's MST algorithm, except after each edge is
chosen, we insert an extra step in which the maximum weight edge between any
pair of distinct components is removed from the graph entirely- thus - it
can never be used as an edge again" is quite sufficient! (Assuming, of course,
that this is the correct
solution to the problem.)
- Don't forget the proof of correctness and runtime analysis. Highlight
the main points of
these arguments. Your job is simply to convince me that you understand the
proof. So (for example)
don't worry too much about base cases in an oral presentation, unless they are
somehow unusual or
especially important. While they are necessary in a formal writeup, they are
usually unimportant in an oral presentation.
Interaction with the instructor
I will randomly assign to each person in your group a problem to present.
Those not presenting should
for the most part remain quiet, unless either the instructor or the person
presenting requests help or
clarification from another group member.
During your presentation, I may interrupt, ask questions, provide or ask for
clarifying comments,
point out flaws or counterexamples, or any other similar behavior. (Don't worry,
I won't usually
throw anything to get your attention.) Usually this can be taken as an
indication that either you
haven't made things clear or there is an error. It might also be that you've
assumed too much of your
tired, stressed, and overworked instructor. In any case, don't panic, because
I'm not out to get you; just
answer the questions to the best of your ability.
Part of the value is that you can get immediate, real-time feedback on your
solutions. However, at some
point it is very likely that you will find out that something is incorrect or
unclear in a problem you
are presenting. Don't panic! You can still get partial credit for these
problems, and may even be able
to fix the solution. Part of the value of this experience is learning to think
on your feet while communicating your solutions.
Within reason, the TA may allow you to react and modify your solutions. However,
full points for
content will only be awarded when initial solutions are correct. Yes, we realize
that this
gives oral presentation an advantage over written homework, since you are more
likely to fix errors and
get partial credit. Enjoy it!