HOMEWORK 1 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; 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) Asserting that there exists a decomposition L1 L2, where neither
is L, is a major error. If they attempt seriously to justify this
incorrect claim, it may be worth up to 3 depending on how far they
got. If they give up before producing a proof that is at least
plausible at first glance, that is a 2 or less.
Typically, there will be some initial discussion about how short
strings must be distributed between L1 and L2 (e.g., 0 and 1 cannot be
in either L1 or L2, and 00 and 11 must be both in L1 or both in L2).
At some point, the argument will likely entail observing that for some
string x in (say) L1, there are two distinct y and y' in (say) L2 for
which xy and xy' must both be in L, and that this forces x to be
empty. There are many different versions of this basic argument, so
read carefully.
If they neglect to observe that both L1 and L2 must contain the empty
string but use this fact in their proof, that is a minor error.
(2) This proof has two directions -- from a DFA, produce an all-NFA,
and vice versa. If they omit the first direction (DFA -> all-NFA)
entirely, that is a moderate error. If they simply invoke the
construction we did for DFA->ordinary NFA, without writing their own
proof, that's probably fine.
The "hard" direction is all-NFA to DFA. They need to address crashing
in an all-NFA (which I specifically posted about to Piazza) as a
distinct failure mode from ending up in a non-accepting state on some
path. If they ignore crashing, and this results in an incorrect
construction, that is a moderate error.
My solution uses the subset construction with altered acceptance
criteria (after fixing the crashing case). Another approach does not
invoke the subset construction but instead constructs a regular NFA
for not-L and then use the closure of regular languages under
complement. Either approach can be correct -- read carefully.
If they pursue the subset construction approach, they need not
re-prove anything we proved in class or reproduce the detailed subset
construction. it's enough to explain how their construction *differs*
(in particular, how it differs in acceptance) and just reuse or assume
the fact of move equivalence. However, if they don't explicitly check
that the altered acceptance criteria do what they want, that is a
moderate error.
(3) Pretty much all the correct solutions I saw use the same basic
construction as I did. Note that I introduce a new start state and
add epsilon transitions from it to the set A of the original machine
M. It's formally a minor error to claim that an NFA *starts* in a set
of states, rather than adding a new start. (Yes, you can get the same
effect in practice by trivially modifying the subset construction.)
An adequate proof for this construction *could* argue inductively as I
did that the appropriate definition of delta leads to an appropriate
definition of delta*. However, I was actually fine with some proofs I
saw that just observed less formally that if M accepts X = a1...an,
then the moves made by M on each ai can be reversed in M^R. You can
decide if you are convinced.
Ultimately, there must be an argument in some form that x is in L(M)
iff x^R is in L(M^R). This may be just a trivial consequence of a
good move-equivalence proof, in which case I don't mind if it isn't
mentioned explicitly. But not proving the construction's correctness
at all is at least a moderate error.
(4)
(a) I've seen good constructions of a machine for L_c either directly
from a machine for L, as I did, or by modifying the machine for L^R
from Problem 3. The same basic modification is needed in each case:
if M can go from p to q on a, then M_c can go from p to q (or M^R_c
can go from q to p) on *any* character b.
The proof need not be as formal as what I wrote (in particular, it
need not use an induction), but it does need to establish what I claim
in my Claim 5. Otherwise, see the general guidelines to evaluate an
incomplete proof.
(b) The basic approach combines the original M for L with the
construct for L_c using the cross-product. My solution uses the
forward version of L_c, but most of the ones I read use a version
based on the backward version above. Either can be OK.
The cross-product construction combines two *DFA*s. It is not
formally defined for NFAs or epsilon-NFAs; rather, if you want to
combine such machines, it is assumed that you convert them to DFAs
first. This is important because the combined machine cannot then
have (e.g.) epsilon transitions. If the construct or proof assumes
that the cross-product machine contains epsilon transitions, that
is a minor error unless it's really important.
(5) There are two basic approaches that I've seen: either combine M
with another machine via the cross-product construction that
guarantees that the result will have more live states, or try to
identify and duplicate a cycle in M. Either can work, but read
carefully.
For either approach, they must prove that the new machine has strictly
more *live* states. As usual, giving the construction with no proof
at all is a 3. A questionable or incomplete proof for a correct
construction would be more like a 4.
If they are confused about what a live state is, so that their
construction adds only states that are reachable from the start but
not on a path taken by any accepted string, that is a serious error.
For solutions that explicitly duplicate a cycle, make sure they add
all necessary transitions (e.g. from the duplicate cycle back to the
states of the original machine). It is a minor error to forget a
couple of transitions in an otherwise good construction.