CSCI 169 -- Fall 2007 -- Final Postmortem

Final Postmortem

CSCI 169 -- D. C. Smolarski, S.J.
Fall 2007
Santa Clara University, Department of Mathematics and Computer Science

NOTES:

Probs 1,2: No general comments.

Prob 3: (B) is incorrect since it includes the null string which is NOT accepted by the automaton.

Prob 4-5: No general comments.

Prob 6: This can also be seen as a permutation problem. Note that a, b, c must appear in any string in that order and so must x, y, z. Thus what is important is whether one goes "UP" or "RIGHT" and we must include three "UPs" and three "RIGHTs" in any string of six characters. Once you determine a string with the correct number of "UPs" and "RIGHTs" then you can fill in the corresponding "UP" letters and "RIGHT" letters in the correct orders. This therefore reduces to a permutation problem with 6 places having 3 UPs and 3 RIGHTS (similar to a problem about how many ways can you take 3 red balls and 3 blue balls out of a bag). The correct answer is 6!/(3!x3!) = 20.

Prob 7: No general comments.

Prob 8: Several had problems with the third list ((E1)(E2 E3)). There are two NODES at the top level, the first pointing to the list of one element (E1) and the second pointing to the list of two elements (E2 E3). Once you have drawn the "TREE" correctly, it should be straightforward to come up with the correct dotted pair notation.

Prob. 9: Several people had final values for j (v-r,ref,name) of 2 rather than 3. When j (n in the function) reaches the value of 2, it is incremented to 3 and so is i, and then the loop is ended.

Prob. 10: This function merely strips all the internal parentheses from a list. I.e., it integrates sublists into one major list without rearranging any nodes.

Prob. 11: See Fortran notes, sec. G-2, to see that F-90/95/2003 needs a double equals sign (as in C/C++) to test for equality. F-90/95/2003 also need parentheses around a logical test within an IF or DO statement. In fixed source format, blanks are ignored, so the original would be read as IFA=BTHEN, which is a legal assignment statement putting the value of BTHEN into IFA (neither of which have to be declared). Thus there would be no error message at this line (although later, an unmatched ENDIF might give an error) at compile time. Some systems may give a runtime error for an uninitialized variable, but others may just preset all variable to zero or use whatever value happens to be in memory.
Most people made no allusion to fixed source format or the fact that this line would NOT have resulted in any error message!

Prob. 12: The model for this problem is found in the notes on pages 6-16, 6-17. Some people overlooked the explicit request to indicate all the handles and "circle them." The answer should have included both the derivation from the given final string aa(a+aa) back to the start symbol and the associated parse tree with leaves at the top and new nodes corresponding to reduction of handles.

Prob. 13-15 No general comments. Prob. 16: See MPI Notes, sec. C.

Prob. 17: No general comments.

Prob. 18: One state needs to be designated as an "accepting" state (cf. pg 6-6). When there exists a production rule B->b, this corresponds to a transition to a "new" accepting state T, from state B given input b. Several people did not indicate any accepting states nor did they indicate the accepting state T.
To find the regular expression, one should have used Arden's Theorem.

Prob. 19: No general comments.

Statistics

High score: 174
Low score: 104
Range: 71 pts
Median (middle score): 146
Mean (average score): 136.6
Standard Deviation: 31.38745
Number who took exam: 5

Scores

  Raw    Normalized
  174	    69
  161	    62
  146	    54
  108	    34
  104	    32

max 200	   100

Distribution

   x              x
   x         x    x

  100  120  140  160
 -119 -139 -159 -179

Number of Perfect Scores per Problem

4/5
3
2
5 "Easiest"
3
1
0*
4
0*
1
0*
1
3
2
0*
2
4
1
3

*all tied for "Hardest" since on one got total points for the problems.