Marking scheme for problem set 2


Total /55

Question 1. /18

(a) /12
        A grammar, which did not respect any of the precedence
        and associativity rules and/or defined mostly nonsense
        expressions got between 0 and 4 marks, depending on
        how much sense I could get out of it. Otherwise:

        -3 (overall) for any ambiguity
        -1 for each associativity or precedence error
        -1 for handling () wrong
        -1 for each other error, for example allowing some expression,
           which should not be allowed

        Comments:
        the most common error here was ambiguity in the grammar,
        as well as handling parentheses

(b) /6
    each /2

    Even if the grammar, defined in part (a), was wrong, the trees got full
    marks if they corresponded to the defined grammar.

    - 0.5 per error in the tree
    - 1 for parsing the wrong string (mostly this was done when the
      grammar defined in part (a) was incapable of producing a parse
      tree for the given expression

    Comments: most people got this part correct


Questions 2 and 3:
   Each function (even helper functions!) must have description AND
   preconditions. 1 mark was deducted for each missing description
   or precondition, up to a maximum of 4 marks for the assignment.
   A solution, which used things foreign to functional programming
   (using setcar!, globals, etc.) got 0 marks, independently of whether
   it was correct otherwise.

Question 2. /12
   each /3

   Since this question did not involve any non-trivial concepts, full
   marks were given only to correct functions with correct Scheme syntax.

   Otherwise:
        0 marks for a solution that does not do anything useful
        -1 for incorrect Scheme syntax
        -1 for any logical error

    Comments:
    I think most errors could be easily avoided by simply trying out
    the code on CDF. For example, something like "car (lst)" instead
    of "(car lst)" or "(+ (cdr a) (cdr b))" instead of
    "(+ (cadr a) (cadr b))"...


Question 3. /25
    This question involved some non-trivial things, so I was not harsh
    on the Scheme syntax here.
    Basically, each solution was marked individually. Most have comments
    explaining why a certain number of marks was deducted.
    As expected, part (d) was most problematic.
    An almost-correct solution, which used all the right ideas, got almost
    full marks. A decent attempt at a solution got about half the marks. Only
    solutions, which demonstrated complete misunderstanding of the concept
    of recursion, got 0 marks.

    (a) /5
    (b) /6
    (c) /6
    (d) /8

Other comments:
    No marks were deducted for poor style and/or inefficient code.