HOMEWORK 2 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) For each part, the proof should follow the standard form for
Pumping Lemma proofs. Given arbitrary n, select a string s with |s| >
n, and given an arbitrary legal division uvw of s, select an m such that
pumping v by m gives a string not in the language.
If they do not designate a *single* string s or a *single* value m,
this might be OK as long as all poaaible s/m that they permit allow
the proof to go through. However, it is a moderate error not to
specify a value for s or m when some of their permitted values don't
work.
It might be that the proof is not clearly and correctly structured,
but you can pick out the s and m and the key bits of the reasoning.
Such proofs should get a 5 if nothing else is wrong. Allow for
flexibility in how the proof is stated, but make sure there are no
logical misstatements (especially express or implied wrong
quantifiers).
(2) There are two directions to prove, whose proofs look quite different.
To show that regularity implies the condition on g, the most reasonable
proofs I've seen essentially use the Pumping Lemma. If they get as far
as showing that, for any given n, there exists a k s.t. g(n + k) = g(n),
that is incomplete (as noted in my Piazza announcement to the class),
but I'll count it a minor error because it was so common. Less correct
solutions are at least a moderate error.
To show that the condition implies regularity, the easiest approach is
to build an explicit finite automaton to accept L, exploiting the cyclic
nature of g to put a cycle in the finite automaton.
If the automaton is correct but does not separately deal with small n
for which the cyclic property of g does not apply, that is a minor
error. If it has a suitable cycle but doesn't quite structure the
chain of 1 states for each value of n correctly, that could be a minor
error. More serious flaws are moderate to serious errors.
For approaches that do not construct an automaton, it will be necessary
to evaluate on a case-by-case basis.
(3) (a) There should be
* a correct and complete enumeration of classes
* a proof that each two classes are pairwise distinguished
* a proof that every string of Sigma^* is in a class
* a correct minimal DFA
The proof bits may look very different from one student to another.
The usual route is to name the classes and then do the proof, but I've
also seen students build a minimal DFA and then argue that (1) it is
correct and (2) each state represents a distinct class of I_L. This
satisfies the completeness and distinguishability parts of the proof,
respectively. Note also that everyone may choose different
representative strings for their class labels. Finally, there are
multiple ways to argue that every string of Sigma^* is in a class;
I don't need a completely formal proof, just an accurate mapping of
strings to classes.
If any one of the four parts above is wrong or missing, that is a
moderate error, except for relatively trivial mistakes (e.g. giving a
wrong distinguishing string for just one pair of classes) that may be
minor errors. Multiple wrong/missing parts would be a serious error.
(b) There should be
* three correct NFAs with three states apiece
* an argument that 3 is the smallest number of NFA states possible
(may be somewhat informal)
* an argument that the three NFAs are actually correct
(may be somewhat informal)
One wrong NFA is a moderate error. Omitting either of the last two parts
is a moderate error.
(4) For (a) and (b), the proof should show infinitely many strings
that are all pairwise distinct, and give a distinguishing string for
each pair. A wrong set of strings is a serious error, while a wrong
distinuishing string may be moderate or serious. Claiming that either
language is regular is a very serious error.
Note that a common mistake in M-H proofs is to show that there are
infinitely many pairs of strings that are distinguished, but not an
infinite number of strings that are *all* pairwise distinct. For
example, if L = {x | x has odd length}, every odd-length string
is distinct from every even-length string under I_L, but there are
still just two classes (odds and evens). If they do this, it is a
serious error.
For (c), the same criteria as for 3(a) above apply, except that they
don't have to build a DFA. Some people might do so anyway, which is
OK but superfluous (unless they find a minimal DFA and use that to
show completeness of their classes).
(5) For (a), any correct example will do. The one I saw most often
was some variant of $(0 or 1)^*$ \beta, which describes the
non-regular language { ww | w in {0,1}^* }.
If the above idea is present but expressed incorrectly, that could be
just a moderate error. Otherwise, if the example is wholly incorrect,
give at most a 2 (and maybe less).
For (b), there needs to be a proof based on the fact that the
allowable expressions R all describe finite languages. I would like
to see a description of how to either build a finite automaton
equivalent to the augmented expression, or of how to turn the
augmented expression into an ordinary regexp.
Note that a general solution must deal with expressions of the form
$R$(S)\beta, where S is a smaller augmented regexp. An inductive proof
is the best way to go, though I'll take a slightly less formal argument
if it is clear.
Failure to handle the general case of an (S) in the middle is a minor
error if everything else is OK. Failure to explicitly show how to
construct a regexp or finite automata is a moderate to serious error,
depending on how vague the solution is, unless they found some other
approach that works (e.g. using Myhill-Nerode).