CS3 SPRING 2001 MIDTERM #1 ANSWERS (prepared by Danny Yoo)

Question 1

We're given the initial defintions:

(define mantra '(cal is great))

(define (weird a b c) '(/ 100 a))

(define (mult-10 w) (word w 0))

(define (my-if the-test the-then the-else)
  (cond (the-test the-then)
        (else the-else)))

For each part, we took off: -2 for errors with an incorrect explanation,
                            -1 for quoting problems
                            -1 for spotting an error, but not given
                             an explanation

Let's go through each part:

(* (+ 2 (/ 7 1)
   (*)  ) )

evaluates to 10.

What caught a few people off-guard was the subexpression:

    (*)

which evaluates to 1, since 1 is the identity element for multiplication.

---

(equal? (quote (1)) (se (1)) )

is an error, because the subexpression:

    (se (1))

tries to unsuccessfully call 1 as a function.
 
---

(if (= 1 '1) + -)

evaluates to a PROCEDURE.

---

(if < 3 4)

evaluates to 3.

'<' is a procedure.  Since this is not false, it's a true value.

---

(and (if #f #f #t)
      'a
      '(b)
      (not (= 1 2))
      mantra)

evaluates to the sentence (CAL IS GREAT).
A few people forgot to remember that 'mantra' itself was a global
variable bound to the sentence '(cal is great).

---

(bl (bf mantra))

evaluates to the sentence (IS).

---

(lambda () m a n 't 'r 'a)

evaluates to a PROCEDURE.

A few people said that this expression would error because neither m,
a, nor n were defined.  Although these symbols aren't defined, Scheme
doesn't look into a function's body until it's called.  This explains
why certain typos don't immediately cause errors in Scheme.  For
example, the following function:

(define (second x)
  (furst (butfurst x)))

doesn't break until we try to call it.

---

(weird 0 1 2)

returns the sentence (/ 100 a).

Quotation in front of a sentence prevents any of its components from
being evaluated: they're treated as literal symbols.  So, within the
weird definition:

(define (weird a b c) '(/ 100 a))

regardless of what input we feed weird, we will always get back the
sentence (/ 100 a).

---

(every mult-10 '(weird 10 2 3) ))

evaluates to the sentence (WEIRD0 100 20 30).
People generally had no problems with this one.

---

(accumulate - (every multi 10 '(3 2 1)))

evaluates to 20.

The subexpression (every multi 10 '(3 2 1)) returns to us the list
(30 20 10)

which, when we feed to the accumulation, evaluates the equivalent
expression:

    (- 30 (- 20 10))

======

Question 2:

The definition we've given:

(define mutual-fun
  (lambda (f g)
    (if (< (f 1)
           (g 1))
        f
        g)))

is a function in explicit lambda form, and can be analyzed more easily
if we transform it to the equivalent implicit lambda form:

(define (mutual-fun f g)
  (if (< (f 1)
         (g 1))
      f
      g))

Part a: Because we have subexpressions (f 1) and (g 1), f and g must
be themselves functions that take in one argument.  Because mutual-fun
returns either f or g back, the range of mutual-fun are functions.
One other thing to notice is that the results of calling f and g on
argument 1 will be compared with the less-than operator.  This implies
that when f and g are called, they need to return back numbers.
Bonus points were awarded for giving more information about the
domain:

    +1 for explaining that f and g must be unary
       (take in one argument).
    +1 for saying that f and g take in numbers.
    +1 for saying that f and g must return numbers. 

---

Part b:

((mutual-fun sqrt sqrt) 4)

is one possible answer.  Because mutual-fun needs to take in two
functions, we need to provide it an appropriate function to work with.
Other possible answers include:

    ((mutual-fun abs sqrt) 4),
    ((mutual-fun first sqrt) 4),

and there are many other answers that are possible.  

We awarded:  +3 for having an expression like the above.
             +2 for realizing that mutual-fun took in two functions,
             where the result of calling mutual-fun must itself be
             called.
             +1 for having two open parentheses or coming up with
             functions.

======

Question 3

The crucial missing test is for negative days or inputting more days
than what's in a particular month.  We can correct this by adding one
conditional clause in the third box which checks both upper and lower
bounds on a date:

((or (< (date-in-month date) 1)
     (> (date-in-month date) (days-in-month date)))
 'illegal-day-supplied)

Placing this answer in any other box will deduce two points, because
then (date-in-month date) has the possibility of returning the
<undefined> value.

    +1 Bonus point for having both bounds correct, in the right box.
    -2 if the answer's in the wrong box.
    -1 if the case study function days-in-month wasn't used; if you
     write out the functionality of days-in-month in full, you're not
     taking advantage of the case study.
    -3 if, instead of using days-in-month, an upper bound of 31 days
     was used instead for each month.  However, acknowledgement that
     this is a rough upper bound will add +1.
    -3 if only a lower bound (< (days-in-month) 0) was checked.
    -1 if a nondescriptive name is used.
    -1 for trivial errors.

======

Question 4

In this question, we were asking you to be able to trace code by hand,
a critical skill for CS3. The ability to "put yourself in the computers
place" allows you to figure out what's wrong with part a. Part b requires
you to think about why, even after fixing part a, it's still wrong and
come up with a creative solution to fix it -- here we were testing not
just a knowledge of scheme but of abstract problem-solving ability:
"Here's what I want to do (in my head), here's code which doesn't do it,
how to I fix it?"

Part a:  Change line 2 with the line:

    (newone total)

To make the notation easier to read, we'll give the name f to the
function returned by lambda:

(define (f total newone)
  (+ (total (* newone newone))))

If we apply the function f on the sentence

    '(1 2 3), we can see the following:

    (f 1 (f 2 3))
    ==> (f 1 (+ 2 (* 3 3)))
    ==> (f 1 11)
    ==> (+ 1 (* 11 11))
    ==> (+ 1 121)
    ==> 122

which is how 122 gets returned.  The idea is that as we're
accumulating starting on the right hand side, we keep a running sum of
squares that we've accumulated so far.  The problem is that we've
misordered the function's arguments; we're accidently applying the
squaring on the running total, which can be corrected by reordering
the parameter list.

Part b:  Replacing line #6 with the expression:

    (se sent 0)

will fix our problem.

The other bug left, given that we make the correction in Part a, is
that we haven't squared the initial rightmost element of our sentence.
The way sum-of-squares works is to go through, one by one, and
square the left element and add it to the total. Well, you probably
realize that you need to start "total" out with some value...what
should it be? Well, we're adding things to the total, so since the
identity of + is 0, we need to initially set total to 0. The way to
do that is to have total be 0 the FIRST time you call lambda.
In order to make things work out correctly, we append an initial 0 to
the sentence.

======

Question 5

Part a:  The expression (mystery '()) evaluates to the sentence:

    (1)

There was no partial credit for this part.  Many people had not
expected the subexpression:

    (every add-one '())

to return the empty sentence, and the majority of answers guessed that
(mystery '()) would return the sentence:

    (1 1)

However, as long as answers were consistent with the rest of the
problem, we did not penalize the other parts.

---

Part b:  (mystery (mystery '())) evaluates to the sentence:

    (1 2)

If your answer to Part a: was the sentence (1 1), then we accepted the
sentence:

    (1 2 2)

as a consistent answer which received full credit.

---

Part c:  Following parts 1 and 2, the idea is to repeatedly call the
mystery function on the empty sentence:

(define (1-to-b b)
  ((repeated mystery b) '()))

If your answer to part a was the sentence (1 1), then your answer
here must compensate for the trailing duplicated number at the end of
the sentence:

(define (1-to-b b)
  (butlast ((repeated mystery b) '())))

which we accepted.

We awarded:

    +1 for using repeated and mystery
    +2 for using the correct form of repeated
    +3 for ((repeated function num) args)
    +4 for a small error
    +5 for a correct solution

Some students didn't see the connection between the first parts of
this problem and part c, but were still able to write 1-to-b with
some creativity:

(define (helper sent)
  (se sent (+ 1 (last sent))))

(define (1-to-b b)
  ((repeated helper (- b 1)) '(1)))

Others felt very uncomfortable about doing an every across an empty
sentence, but still realized how mystery worked, so they used this
solution:

(define (1-to-b b)
  ((repeated mystery (- b 1)) '(1)))

which also works.

---

Part d:  This question could be answered even if parts a-c were left blank.
         Here, we're asking you to take a sentence of some numbers and reduce
         it somehow. The picture from SS p. 110 "Choosing the right tool" 
         tells you the answer.

Here are two possible answers to a-to-b:

(define (a-to-b a b)
  (keep (lambda (n) (>= n a)) (1-to-b b)))

(define (a-to-b a b)
  (every (lambda (n) (+ -1 a n)) (1-to-b (+ 1 (- b a)))))

The first constructs the whole range of numbers from 1-to-b, and then
filters out the numbers that are less than a. The second constructs the
numbers from the difference of a to b and then adds enough to each one
to come up with the same answer.

We gave three points of partial credit for the solution:

(define (a-to-b a b)
  ((repeated bf (- a 1)) (1-to-b b)))

because of the prohibited use of repeated.