Answers to Midterm 2 with Grading Guidelines (GG)

Answers by Danny Yoo (dyoo@hkn.eecs.berkeley.edu) 2001-04-10
Grading Guidelines (GG) added by Pallavi Aravind 2001-04-14

Question 1.

    a) Here's what we do on the first day:

       (dance 1) ==> (L1 B1 R1)

        GG: 1 point for the correct answer (no partial credit)
            NO points if you put a quote in front of the sentence 
                ...or if you had no parenthesis around L1 B1 R1
                ...or if you had extra empty sentences (L1 () B1 () R1)

    b) On the second day:

       (dance 2) ==> (L2 L1 B1 R1 B2 L1 B1 R1 R2)

        GG: 4 points for the perfect answer (as illustrated above)
            3 points for minor errors. E.g., quote in front of the sentence
                     or empty sentence inside
                     or no parenthesis around the answer
                     or if you are consistent with the error from (a)
            2 points for no numbers with L R and B
                     or an extra recursive call
                     and for having the right idea. 
            NO points for all other errors.

    c) We can see that every subsequent dance repeats the previous
       dance twice, and also adds three new dance moves.  That is, if
       (dance 2) contained 9 elements, then (dance 3) must take 
       (+ 3 (* 2 9)) ==> 21 elements.
       
       GG: 4 points for the perfect answer
           3 points if consistent with error in parts (a) and (b)
                    or for generating the CORRECT sentence and NOT counting it
           NO points for all other errors.     

    d) There's no way to do this manually --- we need to look for
       patterns.  Let's take a look at the first few dances

       (dance 1) ==> (L1 B1 R1)
       (dance 2) ==> (L2 L1 B1 R1 B2 L1 B1 R1 R2)
       (dance 3) ==> (L3 L2 L1 B1 R1 B2 L1 B1 R1 R2
                      B3 L2 L1 B1 R1 B2 L1 B1 R1 R2
                      L3)

       The idea is that the very beginning of each dance is a sequence
       of left steps --- (dance 100) starts off with

       (L100 L99 L98 L97 ...)

       which means that the 90th thing we do must be

       L11

       GG: 4 points for the perfect answer
           3 points for L10, L12
           1 point for L<anynumber> or R11
           NO points for all other errors

Question 2.

    a) put-together is a COMBINING patterns, since we're putting
       things together.

       GG: 1 point for the perfect answer
           NO points for all other answers

    b) Here's an embedded recursion definition of put-together:

       (define (put-together s glue)
          (if (empty? (bf s)) ;; or (if (= (count s) 1)
              (first s)
              (word (first s) glue (put-together (bf s) glue))))

        GG: The 6 points for this question were broken up as
            2 points for getting BOTH the base case - (if..)
                      and its return value correct - (first s)
            2 points for correct combiner of final result - (word...)
            2 points for correct recursive call - (put-together...)

    c) Here's a tail-recursive definition of put-together:

       (define (put-together s glue)
          (put-together-helper (bf s) glue (first s)))

       (define (put-together-helper s glue so-far)
          (if (empty? s)            ;; alternative: (if (= count s) 0)
              so-far
              (put-together-helper (bf s) glue
                                   (word so-far glue (first s)))))

       This particular implementation "seeds" the tail-recursive
       function with an initial value for so-far that's nonempty.
       This approach simplifies the base case, at the cost of effort
       needed to "seed" the helper.

       An alternative approach works; here's another way to write
       put-together:

       (define (put-together s glue)
         (put-together-helper s glue "")

       (define (put-together-helper s glue so-far)
          (if (= (count? s) 1)
              (word so-far (first s))
              (put-together-helper (bf s)
                                   glue
                                   (word so-far (first s) glue))))


       GG: The 6 points for this question were broken up as
           1 point for setting up the helper correctly
           2 points for getting both the base case - (if...)
                    and its return value - so-far 
           1 point for the reducing and recursive step
           2 points for combining and returning so-far

    d) Finally, the higher-order function:

        (define (put-together s glue)
          (accumulate (lambda (x y) (word x glue y)) s))

        GG: 6 points for the perfect answer
            4 points for getting the idea right (accumulate) but lambda wrong
              ...lots of people put:
              (accumulate (lambda (x) (word x glue)) s)
              forgetting that accumulate takes a binary function
            2 points for demonstrating that you have some idea
                     by using accumulate/every/lambda intelligently
            NO points for all other answers

Question 3.

    a) The problem is the base case: when we're working with a
       one-element sentence, we can assume it's a number, so let's
       just return that number.

       Replacing line # 2 with   (first s))   does the trick.

       GG: The 5 points were divided into 
           2 points for getting the correct line number
           3 points for making the correction but if you had an
                    error in parens you lost a point here

    b) The only other bug deals with multiplication.  Let's try the
       sample call:

           (calculator '(5 times 5 times 5))

       We expect to see 125, but let's see what calculator does.  It
       hits the else clause, and does the expression:

           (calculator (se (* 5 5) '(times 5 times 5)))

       ==> (calculator (25 times 5 times 5))

       So the bug is that we're not constructing a smaller problem: we
       forgot to go past the first multiplication!  Seeing this, the
       solution isn't bad:

       Replacing line # 9 with (bf (bf (bf s))) will fix everything.

       GG: The 5 points were divided into 
           2 points for getting the correct line number
           3 points for making the correction but if you had an
                    error in parens you lost a point here

Question 4.

Here's a solution to num-parked (you can also take the "not" out and
exchange the order of the "then" and "else" clauses):

(define (num-parked car street)
  (let ((rear (park? car street)))  ;; try to park a car
    (if (not rear)                  ;; couldn't fit a car
	0                           ;; so don't recurse. I could fit 0 cars!
	(+ 1 (num-parked car rear) (num-parked car (- street rear car))))))

        ;; the above recursion is read in english as:
        ;; "count this car (the 1), the cars I can park behind me, and
	;; the cars in front of me. The lower picture on the exam helped
	;; to work out the exact details of the geometry. The street behind
	;; me is simply (- rear 0) which is rear, and the street in front
	;; of me is (- street (+ rear car)) ==> (- street rear car)

There's some subtleties involved: the let is actually necessary for
this problem: every call to park returns a different value due to randomness.

      GG: The 16 points for this question were allotted as per
          2 points for correct LET
          2 points for correct IF condition
          2 points for correct return value
          4 points: 2 for each recursive call to num-parked
          4 points: 2 for correct arguments to each recursive calls
          2 points for the combiner "+1"