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).