;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; CS3 Fall 2000 Midterm 2 Solutions ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Grading Policies are enclosed in square brackets [like this]

******************************* QUESTION 1 ************************************

*** QUESTION 1a ***

Recursion type: Embedded recursion [1/2 point]
Reason: [any are correct, worth 1 point]

1) There's still "work to do" when we hit the base case at the end of
   the recursion.

2) There is an accumulating function ("and") to the left of the recursive
   call. Thus, at every recursive call, we are compiling a sequence of
   these "ands", so that when we're done, we still have to process 
   (and result-of->=-test (and result-of->=-test (and ...

   [ Shaky, or muddy explanations lose 1/2 point ]

*** QUESTION 1b ***

[ In the name you choose, you want to capture three elements, each of which
  was worth 1/2 point: ]

i  ) "every" or "all" or "straight"
ii ) "grades" or "scores" or "a-plus"
iii) "?" at the end (because it is a predicate)

So, excellent names might be:

all-grades-above-a-plus?
straight-a-plus?
every-score-a-plus?
lowest-grade-is-a-plus?

We also accepted the following creative solution:

dream-grade-list?

*** QUESTION 1c ***

[ In general, 1/2 point apiece ]

INPUTS       : grade-list, a simple linear list representing a list of grades
             : and a-plus-min, a number representing a minimum a+ grade
             : [ If you forgot one, you lose 1/2 point ]

REQUIRES     : grade-list contain only numbers, since we are testing <=

SIDE-EFFECTS : none

RETURNS      : #t iff all the numbers in grade-list are at least as high
             : as a-plus-min, (#f otherwise). Returns #t if grade-list is null.

EXAMPLE      : (mystery '(95 100 96) 95) ==> #t ;; All scores are A+ scores

EXAMPLE      : (mystery '(95 100 65) 95) ==> #f ;; Not all scores A+ scores

             : (mystery '() 95)          ==> #t ;; Base case

[ -1 1/2 for thinking you can pass in letters and not numbers ]
[ -2     for thinking it is ANY and not EVERY ]

*** QUESTION 1d ***

(define (mystery grade-list a-plus-min)
  (cond 
   ;; Base case, return #t as requested
   ((null? grade-list) #t)

   ;; If the first grade is an A+, keep looking
   ((>= (first grade-list) a-plus-min)
    (mystery (rest grade-list) a-plus-min))

   ;; We found a non-A+ grade, we can stop and return #f
   (else #f)))

[ -3 for it not being tail recursive or by using functionals ]
[ -1 for each of base case, test, recursive call, else ]
[ -2 for code that is broken ]
[ -1/2 for a redundant case (style) ]
[ -1 for syntax errors ]

******************************* QUESTION 2 ************************************

*** QUESTION 2a ***

Recursion : car-cdr [1 point]
Reason: [ Any are correct, worth 1 point]

We are traversing deeply nested lists
There needs to be a single cond case with both a recursive call to the
  car AND the cdr of the current list.

[ It is not enough to simply say "because the input has deeply nested lists",
  since e.g., "length" is not car-cdr, but it operates on deeply nested lists,
   i.e., (length '(1 (2 (((3))) 4) 5)) ==> 3 ;; length not car-cdr ]

[ -1/2 for only saying "nonlinear" ]

*** QUESTION 2b ***

(define (depth L)
  (cond
   ((atom? L)
    0) ;; [ 1 point ]

   ((null? L)
    1) ;; [ 1 point ]

   ((list? (first L))             ;; [ 4 points, 2 for max, 1 for increment, 
    (max (+ 1 (depth (first L)))  ;;   and 1 for calling both first and rest ]
	 (depth (rest L))))       ;;

   (else
    (depth (rest L))))) ;; [ 2 points ]

It is interesting to note that this could be written 
quite succinctly as follows:

(define (depth L)
  (cond
   ((atom? L) 0)
   ((null? L) 1)
   (else
    (max (+ 1 (depth (first L)))
	 (depth (rest L))))))

and thus, could also be written as (using the format for the exam)

(define (depth L)
  (cond
   ((atom? L) 0)
   ((null? L) 1)
   ((list? (first L))
    (max (+ 1 (depth (first L)))  ;; Note this is the same...
	 (depth (rest L))))
   (else
    (max (+ 1 (depth (first L)))  ;; ...as this. 
	 (depth (rest L))))))

******************************* QUESTION 3 ************************************

*** QUESTION 3a ***

[ There are two possible answers, which are either all right or all wrong. ]

On line # __ 10 __
replacing the symbol or number __ cddr __
with the symbol or number __ cdr __
would cause (roman-sum '(1 5)) to return 9

OR

On line # __ 3  __
replacing the symbol or number __ 0  __
with the symbol or number __ 5 __
would cause (roman-sum '(1 5)) to return 9

*** QUESTION 3b ***

[ Basically, if you got 3a right, the "can you rule it out (yes/no)" is
  worth 2 points, and the reason is worth 2 points. ]

You can't rule out the first one, because we never get to the cond clause
in line 8 because this example has no prefix numbers.

You can't rule out the second one, because we never get to the null
clause.  The null clause is only reached when the number-list has a
prefix as the last two numbers, like (10 1 4) -- said another way, the
second-to-last has to be less than the last number. The last two are
removed with one swoop and the remaining number-list is null. If the
number-list does not have a prefix as the last two numbers, it will
remove a number at a time, and stop on line 4 when the cdr of
number-list is null, returning the car of number-list.

******************************* QUESTION 4 ************************************

*** QUESTION 4a ***

[ There were two main ways of doing this, 95% of the people chose to 
  write ((jeter .75) (sojo .5) (piazza .333)), and 5% of the people chose
  to write ((jeter 3 4) (sojo 1 2) (piazza 1 3)). This second case meant
  people had to do both the division and search in one routine. We gave both
  techniques full credit. ]

STEP III : MAKE-BATTING-AVERAGE-LIST 

[ 1 point for "average" ]

==> batting-average-list (a list of all the "batting-average"s for each player)

[ 1 1/2 point for "average" ]

==> ((jeter .75) (sojo .5) (piazza .333))

[ which is really represented as ((jeter 3/4) (sojo 1/2) (piazza 1/3)) but
  for the purpose of the examples, this is ok ]

STEP IV : FIND-BATTING-CHAMPION

[ -1 for calling step IV "batting-champion", since that was the same name as
  the main top-level procedure we discussed ]

*** QUESTION 4b ***

[ Roughly, 1 point for each of the following ]

;; using our names defined above

(define (batting-champion days-work-list)
  (find-batting-champion
   (make-batting-average-list
    (total-hits-outs
     (accumulate-seasons-work days-work-list))0)))
	    
******************************* QUESTION 5 ************************************

[[[ STYLE ]]]

The following are how we graded the touchy "style" issue. We looked at
five dimensions, each worth 1/2 point each:

V : Variables 

If you used L as the name of a list variable, or poorly named any other
variable in your code, you lost 1/2 point.

F : Functions

If you poorly named a function, you lost 1/2 point.

E : Excess

If you had code that could have been written much simpler, you lost 1/2 
point.

C : Constructor

If you didn't use a constructor where you should have, you lost 1/2 point.

S : Selector

If you didn't use a selector when you should have, you lost 1/2 point.

[[[ Categorical grading ]]]

Grading 5a, 5b, 6a and 6c

Any non-blank answer was graded on a 4-step scale. Perfect answers
garnered full credit. A small error lost 1 point, a major error lost
2 points, and if it wasn't clear you were even going toward the solution,
but at least made a good effort, you lost 4 points (all out of 5).

If you used a lambda, you lost a point.

If you used functionals for 5a or recursion for 5b, 6a or 6b, you lost
full credit. If you used recursion in only part of it, (but not the main
loop) you lost a point.

*** QUESTION 5a ***

;; Recursive version of total-hits-outs
;; 
;; We can write this either embedded-recursively or tail-recursively.
;;
;; The specs say the order of the players does not matter, so I don't have
;; to worry about the reversal that would have to be accounted for in the
;; embedded version.

;; Helper function
;;
;; (seasons-work-to-hits-outs '(jeter h o h)) ==> (jeter 2 1)
;;
;; count is not a functional, so using it saves us lots of pain.

(define (seasons-work-to-hits-outs seasons-work)
  (make-hits-outs (get-name seasons-work)
                  (count *hit* (get-atbats seasons-work))
                  (count *out* (get-atbats seasons-work))))

;; USING EMBEDDED RECURSION 

(define (total-hits-outs seasons-work-list)
  (if (null? seasons-work-list)
      '()
      (cons (seasons-work-to-hits-outs (first seasons-work-list))
	    (rest seasons-work-list))))

;; USING TAIL RECURSION 

(define (total-hits-outs seasons-work-list)
  (total-hits-outs-helper seasons-work-list '()))

(define (total-hits-outs-helper seasons-work-list hits-outs-list-so-far)
  (if (null? seasons-work-list) 
      hits-outs-list-so-far
      (total-hits-outs-helper 
       (rest seasons-work-list)
       (cons (seasons-work-to-hits-outs (first seasons-work-list))
	     hits-outs-list-so-far))))

*** QUESTION 5b ***

;; The easy way
;;
;; (using seasons-work-to-hits-outs helper from the last problem)

(define (total-hits-outs seasons-work-list)
  (map seasons-work-to-hits-outs seasons-work-list))

;; The hard way

(define (total-hits-outs seasons-work-list)
  (map make-hits-outs 
       (map get-name seasons-work-list)
       (map count-hits (map get-atbats seasons-work-list))
       (map count-outs (map get-atbats seasons-work-list))))

(define (count-hits at-bats)
  (count *hit* at-bats))

(define (count-outs at-bats)
  (count *out* at-bats))

******************************* QUESTION 6 ************************************

*** QUESTION 6a ***

;; The easy, fast way, and suggested way

(define (make-batting-average-list hits-outs-list)
  (map hits-outs-to-average hits-outs-list))

(define (hits-outs-to-average hits-outs)
  (make-average (get-name hits-outs)
                (/ (get-num-hits hits-outs)
                   (+ (get-num-hits hits-outs)
		      (get-num-outs hits-outs)))))

;; The hard and slow way (in that you need to map so many times,
;; it's easy to get confused, and each map takes a lot of time for a long
;; list of players.

(define (make-batting-average-list hits-outs-list)
  (map make-average
       (map get-name hits-outs-list)
       (map / 
            (map get-hits hits-outs-list)
            (map + 
                 (map get-hits hits-outs-list)
                 (map get-outs hits-outs-list)))))

;; Our constructor

(define (make-average player average) (list player average))

*** QUESTION 6b ***

;; The suggested way of doing it

(define (find-batting-champion batting-average-list)
  (rassoc (list (apply max (map get-averages batting-average-list))) 
          batting-average-list))
          
;; Another (and by far more complicated) way of doing it

(define (find-batting-champion batting-average-list)
  (find-batting-champion-given-best-avg 
   (apply max (map get-averages batting-average-list))
   batting-average-list))

(define (find-batting-champion-given-best-avg best-avg batting-average-list)
  (list-ref
   batting-average-list
   (position best-avg (map get-averages batting-average-list))))
          
;; Our selector

(define (get-averages averages) (second averages))

;; There are probably many more ways of solving this problem. Look closely
;; at our first solution, it's hard to beat it for compactness and
;; efficiency (while still using functionals)