Rubric DRAFT for Midterm 1

Question 1

Part A:

(define (count-change amount)

    (cc amount 5))

(define (cc amount kinds-of-coins)

   (cond ((=  amount  0)  1)

             ((or  (<  amount  0)  (=  kinds-of-coins  0))  0)

             (else  (+  (cc amount

                                (- kinds-of-coins  1))

                            (cc  (-  amount

                                         (first-denomination  kinds-of-coins))

                                    kinds-of-coins)))))

(define  (first-denomination  kinds-of-coins)

   (cond  ((=  kinds-of-coins  1)  1)

              ((=  kinds-of-coins  2)  5)

              ((=  kinds-of-coins  3)  10)

              ((=  kinds-of-coins  4)  25)

              ((=  kinds-of-coins  5)  50)))

count-change generates  a(n): recursive or iterative process:

Answer:  Recursive (the + before the two recursive calls should have given it away)

Grading: (2 points)

0 points for checking iterative

1 point for arguing that it is recursive just because there is no extra counter or stored variable, remember, iterartion does not require an extra stored variable, although it does use one often.

Part B:

Someone re-wrote count-change to only use pennies and provided the following new definition below.  They argue that now the runtime of count-change is Θ(amount)

(define (count-change amount)

   (cc amount 1))

Answer:

I agree, the new runtime is Θ(amount)

Grading:

0 points for marking disagree

1 for a vague explanation: this included:

    -just saying that there is only one way to count amount with pennies

    -not correctly justifying why the recursive call to (cc amount (- kinds-of-coins 1)) is constant,  

     or not mentioning it at all.

    -not talking about both recursive calls, (only talking about one)

    -general explanations of linear growth that did not directly relate to the problem

    -drawing a basic diagram with no explanation, or an unclear diagram

0 points for a clearly wrong explanation, even if the correct answered was marked.  Example:

    -arguing that cc is only called amount times.  It is called more than amount times, but each

     time, one of the recursive calls is constant.  So it is actually called 2 * amount times, which is

     in Theta(amount) because we ignore constant factors.

The kind of explanation we were looking for was anything that mentioned that cc is still called twice for each call, but that the first call immediately reaches the base case, and so runs in constant time every time, while the other call keeps subtracting one from amount until it reaches zero, so cc is called 2 * amount times, which is in Theta(amount).

Part C:

Is it possible to write a new function count-change-with-pennies that has a runtime of Theta(1) and produces the same answer as calling the version of count-change from Question 1B which uses only pennies?

If yes, provide the code below:

If no, explain why not:

Answer: yes, it is possible

(define (count-change-with-pennies amount)

            1)

Note:  checking if the amount is below zero was fine, also re-writing cc or count-change as long as the runtime was still constant was also fine.

Grading:

0 points for marking “No”

1 point for returning amount instead of 1

0 points for checking yes, but writing no code

0 points for checking yes, but then writing code that ran in worse than Theta(1) time. (Linear or          worse)

Question 2

(define (ninja x) (+ x (+ x x)))

(define (spirit x y) (+ y (+ 0 0)))

(spirit (ninja (+ 1 2)) (+ 3 4)))

Normal order: 3

Applicative order: 6

Applicative order: Evaluate your arguments first.

(spirit (ninja (+ 1 2)) (+3 4)))

(ninja (+ 1 2)). Evaluate (+1 2) to get 3, which is one call.

(ninja 3) is (+ 3 (+ 3 3)), which is 9. This is two calls.

(spirit 9 (+ 3 4)). Evaluate (+ 3 4), which is one call.

(spirit 9 7) is (+ 9 (+ 7 7)), which is 23. This is two calls.

Total number of calls: 6.

Normal order: Expand out spirit first.

(spirit (ninja (+ 1 2)) (+ 3 4)) becomes (+ (+ 3 4) (+ 0 0)). This is three calls. Notice that ninja doesn’t get evaluated.

Total number of calls: 3

Grading: One point each.

Question 3

(define myList (append (list (list 1 2)) (cons 3 (cons 4 ‘()))))

Let’s look at the arguments to append first.

(list (list 1 2)). list creates a list with its arguments as elements. (list 1 2) creates ‘(1 2). Listing that gives us ‘((1 2)).

(cons 3 (cons 4 ‘())). cons creates a pair with its car being the first argument and its cdr as the second argument. (cons 4 ‘()) returns (4 . ()), which Scheme displays as (4)

 (cons 3 ‘(4)) gives us (3 4).

(append ‘((1 2)) ‘(3 4)). append creates a list where the elements are the elements of the argument lists. Therefore we evaluate this expression and we get ((1 2) 3 4)

The box and pointer diagram looks like this:

->[  |  ]->[  |  ]->[  | / ]

     |         |          |

     |        v         v

     v        3         4

   [  |  ]->[  | / ]

    |          |  

    v         v

    1         2

Grading:

Question 6

(define (interesting-doubler ls)

   (map

      (lambda (sent)

         (every

            (lambda (wd)

               (se wd wd))

         sent))

   ls)

)

Important:

-6 if definition uses recursion or any helper functions

-1 for any D.A.V.

-2 for more than one D.A.V.

-2 if no lambda for map

-1 if lambda does not do the correct thing

-1 if forgot to call map with the list

-2 if no lambda for every

-1 if lambda does not do the correct thing

-1 if forgot to call every with the sent

-1 if “word” instead of “se” or “sentence”

Small Mistakes:

-1 if function does not return the correct result

-1 if a call to a HOF (map, keep, accumulate, every, filter) does not include a function

-1 if no every or map completely [- 2 more for no lambda (see above)]

D.A.V. includes:

-map vs. every

-list or cons or append instead of sentence

-list? instead of sentence?

Question 4:

((1) (4) (9))

( (1) ( (4) ( (9) () )))

Question 5:

(define (vector-sum v-list)

  (define (vector-sum-iter v-list result)

    (if (null? v-list)

           result

           (vector-sum-iter

              (cdr v-list)

              (cons 

             (+ (car result) (car (car v-list)))

                 (+ (cdr result) (cdr (car v-list)))))))

  (vector-sum-iter v-list (cons 0 0)))

ANSWER:

(define (vector-sum v-list)

  (define (vector-sum-iter v-list result)

    (if (null? v-list)

           result

           (vector-sum-iter

              (cdr v-list)

              (make-vector 

             (+ (xcor result) (xcor (car v-list)))

                 (+ (ycor result) (ycor (car v-list)))))))

  (vector-sum-iter v-list (make-vector 0 0)))

Question 7A

STk> (((mystery ‘()) 1 1) ‘())

()

STk> (((mystery ‘()) 1 1) ‘(dddd))

(ddddd)

STk> IMPOSSIBLE

(bcd)

Grading:

1 point for correctness

2 points for “impossible”.

3 points for calling mystery with 3 parens.

1 point for calling mystery with 2 or 4 parens (i.e. you didn’t go deep enough or went one level too deep in calling functions).

The idea was that the first 3 points were for understanding what mystery actually did, and the last 4 points were for udnerstanding the domain and range of mystery.

Question 7B

mystery runs in Θ(1) time! This is because mystery simply returns a procedure that takes two arguments.The most common error we saw was Θ(N^2).

Scoring:

2 points for Θ(1)

1 point for Θ(N^2)

0 points for anything else.

We didn’t take points off for not including Θ, using Big-Oh notation (e.g. O(1)) instead, or including constants.

Question 8:

(define (max-n lst n)

        (cond ((= n 0) 0)

        (else (max (max-n (cdr lst) n)

                 (+ (car lst) (max-n (cdr lst) (- n 1)))))

7 points - perfect

6 points - minor errors

5 points - two correct recursive calls, but combined incorrectly

4 points - five point solution with minor errors

3 points - works through the list, attempting to decide whether to add a number at each point

2 points - makes two recursive calls

1 points - major problems