Tazeen Dhedhi --> CS341 Grading

HOME
Project and Midterm Grading Algorithms

Project 2 graded by Tazeen

Question 1

(6) total.

Question 2

(6) total.

Question 3

	(6) total
	(-1) if forgotten to submit y.output

Question 4

	(8) total
	(5) for handtrace : 3 for trace, 2 for identifying at least 2 conflicts correctly
	(3) for automatic trace: 1 for trace, 2 for identifying at least 2 conflicts correctly

Question 5

	(8) total.
	(6) grammar: -2 if not used operators provided by yacc to specify associativity and precedence
	(2) trace

Question 6

(6) total.

Question 7

	(6) total.
	(-1) if not defined unary minus to be right associative
	(-1) if not defined precedence of unary minus to be higher than binary operators

Question 8

	(8) total.
	(6) grammar.
	(2) trace.

Question 9

(6) total. 1 point per question

Question 10

	(10) total.
	(-10) if not stored value of assignment anywhere.
	(-5) for not reading multiple input.
	(-1) for assuming identifier is 1 character long.

Question 11

	(10) total.
	(-2) not assigned anything to $$ for true and false
	(-1) syntax of the grammar is different from the project specification
	(-2) combined boolean expressions and mathematical expressions into one grammar rule
	(-1) for not getting the stored value of the identifier when it is used in a boolean expression
	(-5) boolean expressions don't include comparison operators such as <, >, etc.

Question 12

	(10) total.
	(-2) combined expressions and if statement in one grammar rule

Question 13

	(10) total: 2 points for each question
	(-5) if not turned in anything

Midterm 2

Question 1 a - Graded by Tazeen

	(5) For saying Regular.
	(10) 010 U 010*1
	(-2) for 10 U 10*1, no leading zeros
	(-10) grammar is not regular and generates strings not in L
	(-10) (0U1)*
	(-8) L = odd binary numbers or L = 0*1+
	(-2) doesn't accept 10
	(-5) 10*(0U1)

Question 1 b - Graded by Tazeen

	(5) For saying CF, not Regular.
	(5) CF proof for L = {a^i b^j c^k : i != j V j!=k}
	(5) for not regular proof
	(-3) CF proof: only 1 c and i!=j is mostly right
	(2) not regular proof: w is in L and is in terms of N
	(3) not regular proof: pumping w correctly
	(-1) not regular proof: q is off by 1
	(-3) not regular proof: think L'=a^N b^N c^N

Question 1 c - Graded by Tazeen

	(5) For saying not CF.
	(3) w is in L, and in terms of M
	(2) for doing the (1, 1) case correctly
	(5) for doing the rest of the cases correctly

Question 1 d - Graded by Tazeen

	(5) For saying not CF.
	(3) w is in L and in terms of M
	(7) for showing all the cases correctly
	(5) if haven't said not CF, but said not regular and done a correct proof for not regular
	(2) not regular proof: w is in L and in terms of N
	(3) not regular proof: pumping w correctly

Question 2 - Graded by Dr. Rich

	(3 - 5) For having a few ideas right but an overall answer that wasn't a decision procedure (i.e., it wouldn't halt, the steps weren't operations, etc.).
	(15 minus the following) If the answer was an actual decision procedure
	(-8) if you tried to do it all with PDA's and it wasn't right
	(-4) if you just asserted that there exists a grammar for the intersection of the two languages without specifying a procedure for finding it.
	(-5) if everything was right but you didn't try enough strings in the final step.

Question 3 a - Graded by Atri

	(-6) Uses a rule like aNaNa expecting N to produce strings of the same length.
	(-4) If aa & bb are the only even length strings generated.
	(-1) if the grammar does not generate a & b.

Question 3 b - Graded by Atri

	(-8) Accepts strings not in the language.
	(-7) Accepts a (small) constant number of strings.
	(-4) Accepts (an infinite) subset of strings.

Question 3 c - Graded by Atri

	(-8) Incorrect choice of w.
	(-7) Correct choice of w but the proof assumes the length of y.
	(-6) Correct choice of w but incorrect argument.
	(-4) Half of the cases are not considered.

Question 4 a - Graded by Atri

	(-4) If the answer says that M(L) is the set of substrings of L.
	(-3) If the answer is a (strict) subset of (a U b)*

Question 4 b - Graded by Atri

	(-13) Mentions M(L) is subset of strings of strings in L but argument is wrong.
	(-10) Starts by converting the grammar of L to CNF but replacement rules are incorrect.
	(-8) If the state of the stack is not taken care of when epsilon transitions are introduced into the PDA for L.
	(-8) If using the CNF approach just adds epsilon transition for each non-terminal.
	(-6) Transitions in the modified PDA are incorrect.
	(-6) If the newly constructed PDA just accepts Prefix(L).
	(-4) If the newly constructed PDA just accepts Suffix(L).

Question 5 a - Graded by Atri

	(-4) L1 is not CF
	(-2) If L2 and L3 are correct and L1 is CF but the description of L1 is wrong.

Question 5 b - Graded by Atri

	(-6) L1 is not a subset of L2 but L1 is regular and L2 is CF.
	(-4) L1 is a superset of L2 (and the answer says so).
	(-4) Says L2= a^n b^m but no relations between n and m is given.

Question 6 a - Graded by Dr. Rich

(1) for each of the three answers: 11, 121, 131

Question 6 b - Graded by Dr. Rich

(2) for any correct answer

Question 6 c - Graded by Dr. Rich

	(15) total
	(5) for getting rid of epsilon productions
	(5) for getting rid of unit productions
	(3) for getting rid of terminals in right hand sides of length greater than 1
	(2) for getting rid of right hand sides of length greater than 2

Midterm 1

Question 1 a - Graded by Atri

	-2: If the expression generates epsilon.
	-1: If some other alphabet is used.

Question 1 b - Graded by Atri

	3: for saying Yes.
	7: for the proof.

Question 2 a - Graded by Tazeen

	-2: For assuming that the first character has to be a.
	-1: If the answer is b( abb U epsilon) (aUb) or if it is b(abb)(aUb)
	-2: If the answer is b* (a U epsilon) bb (aUb)*.
	-3: If the answer is babb U (aUb).

Question 2 b - Graded by Tazeen

	-2: If assumed that the first character has to be a.
	-1: For each missing or incorrect equivalence class. There are five classes altogether.

Question 2 c - Graded by Tazeen

	-2: For assuming that the first character has to be a.
	-2: Accepts aa, aba

Question 2 d - Graded by Tazeen

	-2: For assuming that the first character has to be a.
	-1: More than one terminal on the right hand side.
	-4: More than one non-terminal on the right hand side.
	1: For getting b*
	1: For getting b* before the rest of the string.
	1: For getting b* abb
	1: For getting b* abb (aUb)*

Question 3 a - Graded by Atri

	5: For saying Not regular
	10: For the proof.
	-3: If complement of L ={xy=z: x,y,z \in {0,1}+, when viewed asbinary numbers, z=xy}
	-9: If a particular form of y is assumed in the pumping lemma proof.
	-10: If pumping lemma proves takes a w not in the language.

Question 3 b - Graded by Atri

	5: For saying Regular
	10: For the DFA/regular expression.
	-5: Accepts a "big enough" subset of L.
	-8: Accepts a "small" (but still infinite) subset of L.

Question 3 c - Graded by Tazeen

	7: For saying Regular
	-4: For saying L = b*aa
	-2: For saying L = b*aa U ab

Question 3 d - Graded by Tazeen

	7: For saying Not regular
	3: w is an element of L, in terms of N, the pumping constant.
	2: For giving the correct y.
	3: Rest of the proof.
	-1: Pumping up and down.
	-3: Proof for y in regions that it can't be in.
	-2: Picking w = 0^N 1^N-3. This assumes that N is at least greater than or equal to 3.
	-1: For saying that after pumping, the length of the string increases by q\|y\|. It should be (q-1)\|y\|.

Question 4 a - Graded by Atri

	-4: If the Splitable condition fails for "many" strings.
	-2: If the Splitable condition fails for constant number of strings.

Question 4 b - Graded by Atri

	2: For saying no.
	6: For proof.

Question 4 c - Graded by Atri

	2: For saying yes.
	6: For proof.
	-6: If L = {a^n b^n: n is even}
	-2: If the splitable condition fails for a constant number of strings.

Question 5 - Graded by Dr. Rich

	-5: if mistakes in using the E(q) function.
	-2: if took the complement of the resulting machine.

Question 6 - Graded by Dr. Rich

	3: points for saying that the first step is to convert the regular expressions to machines, even if nothing else was right.
	-4: if basically correct but forgot to consider only even length strings.
	-3: if check strings of length up to N but not 2N (since this could miss some)

Project 1

	15 points for each of Elaine's test cases. (+) -5 if one input string has the wrong result. (+) For machine 3 & 4 (-5) is no error/warning message is flashed but underlying assumption is mentioned in the user doc.
	25 points for user documentation. (+) 10 points for input and output formats. (+) 5 points for epsilon handling. (+) 5 points for algorithm used. (+) 5 points for the data structures used.