;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; UC Berkeley CS3L 2008Fa Midterm Solutions ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;; ;; QUESTION 1 ;; ;;;;;;;;;;;;;;;; (accumulate + (every cost (keep food? (keep usa? shoplist)))) 1 point for accumulate + 1 point for every (with cost) 1 point for keep (with food?) 1 point for usa (with usa?) 1 point for cost, food? and usa? -1 point each for missing a HOF/procedure. -1 point for domain and range issues for a particular HOF. -2 points for swapped calls ;;;;;;;;;;;;;;;; ;; QUESTION 2 ;; ;;;;;;;;;;;;;;;; What is the domain of mystery? x is a FUNCTION whose domain is a WORD and whose range is a WORD OR A SENTENCE y is a WORD -1/2 a point for each capitalized word/phrase for a total of 2 points. No partial credit. If the solution was "word", "word or sentence" was not accepted. What is the range of mystery? A function whose domain is a WORD and whose range is a WORD. 0 points if it doesn't mention that it returns a function. 1 point for each capitalized phrase Show a call to mystery ((mystery (lambda (x) '(cal)) 'beats) 'stanford) -2 points if it doesn't return the correct answer additional -1 point if the call returns a procedure and not a word -2 points if stanford is crossed out, problem becomes all-or-nothing ;;;;;;;;;;;;;;;; ;; QUESTION 3 ;; ;;;;;;;;;;;;;;;; If they include a quote in the output, half off on either part a or part b, usually in part a. If they miss part a, it is docked in part b. No points were docked for double quotes since word returns those in special cases. If they quoted every single character, an entire point was taken off in part a or part b. a) x---o  all or nothing b) xx---o--o If they got part a wrong, they can still get credit on part b if they insert part a in [day 3]. If the second half is wrong, they lose a point. 1 point for "x [day 3]" 1 point for "- [day 2] o" x| [day 3] | - | [day 2] | o c) "x x x . . . x x o" 1 point for first half "x x x ..." 1 point for last half "... x x o" d) IMPOSSIBLE, POSSIBLE, IMPOSSIBLE 1 point each for the answers If they missed points here because of tracing incorrectly in part a and part b, they will not lose a point for that particular pattern that was wrong. ;;;;;;;;;;;;;;;; ;; QUESTION 4 ;; ;;;;;;;;;;;;;;;; a) Change the specifications 1 point for "change spec/input/requirement" 0 point for "don't call it", "modify call" b) () 1 point for () -1/2 point for '() - extra quotes 1/2 for line #2 1/2 for (se in-a-row- letter) c) (compress 'ox), or (compress 'xxo) with an explanation 1 point for (compress 'ox). We also accepted (compress 'xxo) as long as you provided a good explanation about why this answer reveals 2 bugs: 1) count isn't reset, 2) letter isnt changed (worth 1/2 point) -1/2 for (compress ox) - no quotes -1/2 for (compress 'oox) - inputer longer than 2 char 1 point for correct return: (1 o 1 o) from above 1 point for expected return: (1 o 1 x) from above 1 point for line #8 1 point for (compress-helper (bf w) 1 (first w)) or (compress w) -1/2 for w instead of (bf w) -1/2 for 0/in-a-row instead of 1 -1/2 for w instead of (first w) Total 1 point deduction d)2000 1 pt all or nothing e)EMBEDDED 1 pt all or nothing ;;;;;;;;;;;;;;;; ;; QUESTION 5 ;; ;;;;;;;;;;;;;;;; a) (accumulate + n) 1 Point for correctness, all or nothing Many students did not recognize that accumulate could do a procedure on words, and did something like (every se n) first. This is unnecessary, but we ignored it for grading this time. b) (define (repeateds-until f pred? input) (if (pred? input) 0 (+ 1 (repeateds-until f pred? (f input))))) 1 Point for conditional .5 Point for base case 1.5 Points for the combining and recursive call -.5 Points for each minor error (max of -1 Points) c) (every 9* (( repeated (lambda (s) (se s (+ 1 (last s)))) (- n 1)) (se 1))) ) 1 pt for complete correctness 1 pt for every 9* earns a point. 1 pt for generating an actual sentence 0 pts for merely adding or subtracting from a number n times -0.5 for each minor error d) (every (lambda (i) (repeateds-until add-digits 9? i)) (9s n)) 1 pt for correct idea for the solution. 0.5 each for add-digits, 9?, i and (9s n) -1pt for omitting lambda (usually led to an additional -0.5 for omitting i) -1pt for omitting every 0 pts was awarded for using add-digits once, non-recursively.