Grading Scheme for Homework 1 A student gets 20% for writing "I do not know how to solve this problem". If a student gives more than 1 answer to a problem, only one of them chosen at random for grading. Any solution which is illegible will not be graded. --------------------------------------------------------------- Question 2: 10 points There are 10 subquestions and each is out of 1 point. Basically, 1 point if their answer is correct with a correct proof, 0 if the answer is incorrect or if the proof is bad. In general, partial marks are not given, but if a student write "I do not know how to solve this", give 1/5 of a point on that part. The following definitions of the complexity measures could be used: f(n) is O(g(n)) if there exists c>0 and interger N such that for all n >= N, f(n) <= cg(n) f(n) is Omega(g(n)) if there exists c>0 and interger N such that for all n >= N, f(n) >= cg(n) f(n) is Theta(g(n)) if there exists c,d>0 and interger N such that for all n >= N, 0 <= cg(n) <= f(n) <= dg(n) f(n) is o(g(n)) if lim as n->inf of f(n)/g(n) = 0 f(n) is omega(g(n)) if lim as n->inf of g(n)/f(n) = 0 And the basic relations: if f(n) is o(g(n)) then f(n) is O(g(n)) And if f(n) is O(g(n)) and if f(n) is Omega(g(n)) then f(n) is Theta(g(n)). Any other facts or relations must be proven. Some the students want to use: if lim as n->inf f(n)/g(n) = c > 0 then f(n) is O(g(n)) log n is O(n^k) for k>=1 To use facts such as these, they must be proven somewhere on the assignment. A proof which uses an unproved fact should get a 0, but if a fact is used more than once in their homework, only give a 0 for the first time (assuming the fact is true) it is used. So the student will lose at most 1 point for each unproven fact. --------------------------------------------------------------- Question 4: 10 points The student gets 2/10 for writing only "I do not know..." There are 5 points for the Turing machine, and 5 points for the argument. Any TM model seen in class or tutorial may be used; but to use a Stay state for multihead, a justification is required (the Stay state for multitape was proven on the last quiz), -1 if not justified. TM structure is worth 2 points: -1 if structure (type) of the TM used not clear -1 if either Sigma or Gamma are missing or incorrect -1 if the input encoding is not clear or not valid for the TM type chosen -1 if Q not stated or incorrect or incomplete The transition function is worth 3 points: -3 if missing or you cannot make sense of it -1 if transition function is incomplete -1 if not sufficiently documented (either state or transition comments missing, or you can't make sense of it) Though deductions may be more than 5, do not deduct more than 5 for the TM itself. In this question, the students were to give the complete transition function. It is ok if the students use some shorthand in their description as long as the meaning is clear. The students should not skip steps by writing things like: "First copy the input string to the second tape". They need to provide the transitions to do that. Arguing the TM correct is worth 5 points. A formal proof is not required, but the argument should be convincing. You should be able to extend their argument to a formal proof by filling in the details. 5: A completely correct and concise justification that can easily be extended to a full proof. 4: The justification seems to be missing a few points or is long, rambling, or unclear. For example, an otherwise good justification which fails to show that strings in the incorrect format are rejected. Or a justification which covers all the bases but is quite long and hard to read. 3: The justification is basically correct, but is missing some key points. For example, it is not obvious that the machine must halt or reject strings which are not in the language (either because they are not in the correct format or because p does not divide q). 2: The justification is wrong. For example, the student fails to show that the machine will accept when p divides q. 1: The student only wrote a description of the TM. 0: Doesn't even describe how the TM works. Shows no understanding. --------------------------------------------------------------- Question 9: 10 points 5 points for "if" direction and 5 points for the "only if" direction. For each direction, the proof will receive a score of 3-5 if it is generally correct, and a score of 0-2 if the proof is incorrect. 5: A correct and concise proof. 4: A correct proof which is missing a few minor details, or a long, rambling, or convoluted proof which is otherwise completely correct. 3: The proof idea is correct, but is missing many points or is written so that it is unclear. 2: The proof is incorrect, but is a good effort and shows understanding of the material. For example, the proof is off base, but the student is correctly manipulating Turing machines and languages. 1: The proof is clearly incorrect, but there is some understanding of the material. For example, at least the student knows what decidable and semi-decidable means. 0: The proof is unintelligable or shows no understanding of the material. Possible errors: The student proves one direction but fails to prove the other direction. In this case, you should grade the one direction out of 5 and give 0 for the missed direction. A common problem will be the students try to create D but fail to get around the halting problem. For example, they may try dovetailing C or they may have y be a bit which indicates whether x is in C. If these "proofs" show no other obvious errors, they should get a 2. --------------------------------------------------------------- Question 10: 10 points A correct proof will score 6-10 points, and an incorrect answer will score 0-4 points. 10: The proof is correct and concise. 8: Minor errors or proof is overly long and convoluted. 6: Significant errors but still mostly correct. 4: Has the right idea, but the proof is incorrect. For example, is trying to use A_TM, DIAG, or HB in a logical way, but doesn't quite work. 2: Has some understanding of how to approach the problem, but the answer is clearly incorrect. 0: The student is clearly lost or you can make no sense of it. Graders comments: Many students did not adequately comment their Turing machine transitions, making it very hard to read.