HOMEWORK 4 GRADING GUIDELINES
These guidelines describe how to evaluate and communicate your
evaluations of students' homework problems. For general instructions
on how to record comments and scores, and how to communicate concerns
back to the instructor, please see
http://classes.engineering.wustl.edu/cse547/ehomework/grading.html
GENERAL GUIDELINES AND EXPECTATIONS
(1) Every problem should receive not only a numerical score (see below
for the scale) but also polite, informative comments explaining any
shortcomings that led to a reduction in score. These comments must be
made, and the score must be recorded, as comments on the PDF itself.
The score should also be recorded on the spreadsheet included in your
Box folder.
(2) Follow the per-problem guidelines when assessing if errors or
omissions in the solution are minor, moderate, or major for scoring
purposes. Within those guidelines, I expect you to use good judgment,
and to be consistent across assignments. CONSISTENCY BETWEEN
ASSIGNMENTS AND BETWEEN GRADERS ON THE SAME PROBLEM IS VERY IMPORTANT.
(3) Do not take off points for careless, trivial mistakes, but do note
them if you see them. Do not nitpick grammar, spelling, handwriting,
or teeny weeny notation bugs. If *in the aggregate* these issues make
a solution very hard to read or understand, please leave a note to us
about it on the spreadsheet, but try to grade it as best you can.
(4) Solutions that do not follow the same approach as the instructor's
solution are fine, provided they are correct and well-justified.
There is often more than one way to solve a problem. If you see a lot
of solutions taking an approach that you consider to be unusual or
questionable, please let the instructor know ASAP.
(5) A proposed construction must always be justified. We have
established class norms for what constitutes an adequate
justification, which includes some sort of formal proof. Within this
framework, however, there is a lot of wiggle room as to how much
detail is sufficient. (The instructor's solutions tend to be somewhat
overly detailed!) A good guide is whether you would find a given
assertion surprising -- if so, and it is not backed up by
justification, the solution has an issue. "Obvious" observations need
not be justified. Induction on string length or number of moves is
often a good way to formalize an intuition about an automaton's
behavior on strings, but the proof may be persuasive even without it.
(6) If you cannot understand the approach (right or wrong) that the
student took to solving the problem after five minutes of trying,
please ask one of the TAs to look at it. If they can't help either,
leave a note on the spreadsheet for the instructor to look at it.
GRADING SCALE
Each problem will receive a score of between 0 and 6. No fractional
scores should be given. Problems with multiple parts should receive a
separate score for each part.
The meaning of the scores is as follows:
6 - close to perfect. Trivial errors or omissions that are
clearly typos or math errors (e.g. the odd off-by-one)
and are easily fixed are OK. Trivial notational errors are
also OK for a "6" solution.
5 - minor errors or omissions that are more than just typos and
indicate wrong thinking or missing pieces, in an otherwise
high-quality solution.
Examples of minor errors include important confusion between
states and sets or strings and classes; leaving out a small,
non-core part of the transition function for a defined automaton;
or omitting a minor case in a proof.
4 - a lot of minor errors, or at least one moderate error. The
solution is salvageable but clearly has issues.
Examples of moderate errors include leaving out an important case
in an otherwise correct proof; translating a clearly correctly
described intuition into a broken but salvageable formal
construction; leaving off the easy direction in a proof that
requires an iff; or giving a proof where the logic is generally OK
but makes an important unjustified or wrong step.
3 - multiple moderate errors or a serious error -- the solution is
broken or seriously unjustified.
Examples of serious errors include giving a good intuition and
construction, but little to no proof of correctness; leaving off
the hard direction in a proof that requires an iff; or giving a
very broken construction or incomplete justification that implies
wrong ideas about how to solve the problem.
2 - multiple serious errors; a very broken solution
Giving a good intuition but offering *no* supporting construction
or proof would be a 2, unless the missing details are super-obvious
(in which case, it would be a 3). Severely wrong intuition may be
a 2 or 3 depending on how far the solution gets before failing.
1 - hopeless / incoherent solution
Wrong intuition with no supporting construction or justification is
at most a 1.
0 - nothing submitted, or no attempt to solve the general problem
(as opposed to one or a few specific examples)
I would advise the graders for a given problem to TALK TO EACH OTHER
ensure that everyone has roughly the same understanding of how to
apply the grading scale.
I will provide some guidance for each problem on common minor,
moderate, and major errors.
SUGGESTED APPROACH
Start by looking for the intuition or, if one is not given, the
construction. Is it similar to something you recognize? If not, is it
obviously wrong or incomplete? Different solutions may give quite
different levels of detail -- if you can figure out what is going on,
this is perfectly OK.
Look for the correctness proof. If it tries to prove equivalence of
two things, are all the steps iff, or does the proof have two
directions? If it tries to justify the correctness of an automaton
construction, does the justification apply to arbitrary input strings?
Overall, are the proofs readable? Are any important assertions made
without justification?
You will probably find many solutions that are incomplete or go astray
at some point.
COLLABORATION POLICY ISSUES
If you see two or more solutions that look suspiciously similar,
please privately let the instructor know the names of the students
involved. Note that I'm looking for similarities that are beyond what
you might expect based on following the course collaboration policy,
which allows students to discuss their approach verbally in detail.
If you want me to act on a possible case of cheating, the evidence
needs to be fairly convincing.
------------------------------------------------------------------
* PER-PROBLEM GUIDELINES
(1)
I need to see a construction of some kind, i.e. how to turn a TM that decides
L in time T(n) into one that decides in time t(n)/c. Note that it is not
sufficient to manipulate the big-O notation -- t(n) is not the same thing as
O(t(n)). Attempting to "hack around" the question in this way is worth at
most 2.
There are two parts to the construction: compressing the input, and
compressing the computation on the compressed input. The first takes
Theta(n^2) time for a single-tape TM. If they did it with a 2-tape TM
in linear time, this is equivalent -- don't take off. I don't care
much about the details of how tape compression was done as long as
it is correct and runs in the desired time. The key thing is to
store m symbols in one tape cell by expanding the alphabet.
The hard part is how to compress the move function. If they claimed
that simply operating on the compressed input, with no further
innovation, is sufficient, that is a major error -- a TM operating on
the compressed tape could take along time if the computation shuttles
back and forth between adjacent compressed tape cells. Some kind of
trick, involving tracking the contents of the cells adjacent to the
current cell, is needed to avoid this bad case.
Some people may claim that 8 moves of the compressed TM are needed to
simulate up to c moves of the original, while others may claim it's 6
moves. I think it *is* possible to do it in 6, but don't take off if
they did 8. I don't think it is possible to do it in less than 6 for
the strategy described in my solution.
Finally, there is some subtlety in achieving the target speedup factor
of c. If it takes d moves of the compressed TM to simulate m moves of
the original, that suggests a speedup of d/m, so one would choose m
large enough to make d/m <= 1/c. But there is an additive quadratic
cost to compress the input in the first place, so the actual
compression ratio needs to be even bigger to overcome this cost.
Achieving any speedup provably > c on the main simulation is
sufficient, because t(n) grows strictly faster than n^2, and for small
n (where t(n) > n^2), we can just decide these strings in the finite
control in linear time. Failure to obtain the right ratio for an
otherwise OK construction is a minor error.
(2)
The key things here are (1) observation that f maps exponentially
many formulas to polynomially many strings 0^k, since it does not have
time to write a larger-than-polynomial-sized string, and (2) use of f
along with enumeration of partial evaluations to merge partially
evaluated formulas that map to the same value under f, so that only
polynomially many such formulas need be checked to determine if phi is
satisfiable.
Any top-down exploration order of the tree of partially evaluated
formulas can be made compatible with memoization via f. The
breadth-first approach in my solution is easy to follow, but you could
also hash each unique value of 0^k and go (say) depth-first. Be sure
to give credit for correct approaches not like my solution.
If they actually attempt to decide problem A, that is a serious error
-- it's assumed hard to do so. If they potentially evaulate f more
than polynomially often, or do exponential enumeration work by mistake
even with polynomially many calls to f, that is a moderate to major
error depending on severity. Confusion about how to check
satisfiability by enumerating partially evaluated formulas is likely a
moderate error.
(3)
I need to see (1) a proof that LPFP is in NP, and (2) a reduction
to LPFP from an NP-hard problem. The reduction must include a
construction of an LPFP instance from the hard problem instance
(which takes only polynomial time in the instance size), and
an iff proof that the LPFP instance is solvable iff the original
hard problem is solvable.
If the NP part of the proof is missing, that is a moderate error. If
it is broken, that may be a minor or moderate error. If they reduce
in the wrong direction (e.g. LPFP to 3SAT), that is a major error. If
they omit one side of the iff proof (or claim "it's obvious" without
explanation, i.e. how to get a path from a satisfying assignment or
vice versa), that is a moderate error; if they omit both, that is a
major error.
If their construction for the reduction is broken, that is a moderate
to major error depending on how bad the breakage is (i.e. did they
have the right idea, or is it completely misguided?).
If they are unclear on how long the path must be in the LPFP instance
in a way that can't reasonably be inferred from the rest of the proof,
that is a minor error.
If they omit source and sink vertices s and t, but the construction is
still correct, that is fine. LPFP as formulated here does not
designate a particular start and end vertex.
Note that some people might put extra constraints on the forbidden
pairs (e.g. the second vertex occurs at a level after the first) or
add additional bits to the graph. If this doesn't mess up correctness
or the running time but is merely superfluous, comment but don't take
off.
(4)
There are at least two good approaches: treat the 2-clauses as implications,
and verify that it is not possible to get from x to not-x AND from not-x to
x; or use resolution to combine clauses and see if a contradiction arises.
The important thing is that the solution should include (1) a correct,
polynomial-time decision procedure, and (2) a proof that the procedure
actually works for all 2CNF formulas. Giving (1) but not (2) is worth
a 3.
With respect to the implication graph, it is possible to formulate the
decision procedure in terms of strongly connected components or (as in
my solution) not. Either way, it should be clear why a graph with the
two specified paths for any variable implies an unsatisfiable formula
(this is the easy direction) *and* why a graph without such paths
permits a satisfying assignment. If they only do the first of these
arguments or botch the second, that is a moderate error.
Note that it is not suffcient to have a path from x to not-x OR from
not-x to x. Both paths must exist for unsatisfiability. Trying to
work with just one is a major error.