;;;;;;;;;;;;;;;; ;; META-COMMENTS ;;;;;;;;;;;;;;;; Overall, we were pleased with the results. Students should use their raw subtotal score for the most accurate feedback of their performance. Students whose subtotal was 13 or lower need to see a TA in office hours to make sure they understand what they were doing wrong. ;;;;;;;;;;;;; ;; QUESTION 0 ;;;;;;;;;;;;; Assume you don't know what recursion or higher-order functions are. Would you be able to do the following? (circle YES or NO) a) Return the number of words that end in ing in an arbitrarily long sentence. Example: '(sing dance bring) has 2 words that end in ing. NO. Without recursion and higher-order functions we have no techniques to traverse an arbitrarily long sentence. We CAN ask for the length of the sentence (using "count"), a particular element (using "item"), or for the number of words that are exactly equal to a particular word (using "appearances"), but we can't query for the number of words that match a certain pattern, like "ending in ing". Folks who didn't know what higher-order functions (HOFs) were either looked them up in the book, found them in the back inner cover, or asked a TA. Those who didn't have any idea what they were also probably didn't know what "every" and/or "keep" were and got the question right. Those who knew what keep and every were but didn't know what HOFs were probably missed part (a). These folks may have seen keep and every when they were shown in the demonstration of the "functions" program, but didn't know they were HOFs (and might not have known what the word meant at all!). In general, if you don't know what a word means, either look it up in your book or ask a TA. However, HOFs WERE mentioned on page 23: "you'll see that higher-order functions (functions of functions) like KEEP and EVERY can make programs much easier to write". b) Return the sum of the first million prime numbers. YES. Sure, we CAN write this function. We could either write it using traditional means: (define (sum-of-first-million-primes) (+ 2 3 5 7 11 ...)) or we could do the calculation ourselves on a (BIG!) piece of paper and write the function like this: (define (sum-of-first-million-primes) 7472966967494) ;; GRADING -1 for each wrong answer ;;;;;;;;;;;;; ;; QUESTION 1 ;;;;;;;;;;;;; (define (ucb) 'cal) ;; go is the identity -- whatever comes in goes out unchanged! (define (go bears) bears) (define (iftest b) (if b (if (not b) 1 2) 3)) ;; a) (se (ucb) '(ucb) (go (go 'bears))) ;; (ucb) is a function call which returns cal ;; '(ucb) is a sentence ;; (go 'bears) is a function call to the identity, returning bears ;; which is passed into go which returns bears. (se (ucb) '(ucb) (go (go 'bears))) (se (ucb) '(ucb) (go 'bears)) (se 'cal '(ucb) 'bears) (cal ucb bears) ;; b) (first (last (bf (bl '(cal is number one))))) (first (last (bf '(cal is number )))) (first (last '( is number ))) (first 'number ) n ;; c) (and (or (not ____) '#f) 'berkeley) ^^^^^^^^^^^^^^^^^^^ ;; this has to be true to get to berkeley ^^^^^^^^^^ ;; (or x #f) ==> x, thus x must be true ^^^^ ;; (not x) ==> true, thus x must be #f! #f, i.e. (and (or (not #f) '#f) 'berkeley) (any expression that evaluates to #f is also ok, but #f or false is optimal) ;; d) ;; Remember, 4 is TRUE, therefore (iftest 4) becomes (if 4 (if (not 4) 1 2) 3)) ;; 4 is true, thus follow the "then" branch (if (not 4) 1 2) ;; (not 4) is #f, thus it's the "else" branch 2 ;; ==> 2 ;; e) (define (mystery bob) (even? (word bob 2))) DOMAIN "word" takes words, but this is passed to "even?" which only takes integers (a subset of words). Thus, the doman of "mystery" is only integers. We accepted "numbers", as that is a necessary but not sufficient description of the domain. (E.g. 3.14 is a number but is not in the domain of even?.) Many realized that you can pass in the empty word as well. "positive numbers" was accepted, but it works for negative numbers as well. That is, if you pass in -1 (odd, negative), it becomes -12, which is even! "expressions that return numbers" is wrong. Yes, it is the case that you can feed expressions that return numbers into mystery, e.g., (mystery (+ 1 2)), but that is not the domain. The domain is what data types (or subset of a data type) are valid input to a function. "functions that return numbers" is even worse. What these students probably meant to say was "calls to functions that return numbers", but this isn't right for the same reason mentioned above. We'll see pretty soon that you can actually pass functions in as input to other functions. Thus, someday the domain might actually be "functions that return numbers", but not yet. RANGE The range of even? is booleans, thus the range of mystery is booleans. Clever students also may have realized that the return value of mystery is always #t, so that is even a more descriptive range. Students who answered "integers" or "empty word" for the domain AND answered "#t" for the range were granted one bonus point. "error" is not a return value. Range is defined by what are the set of return values given all input in the valid domain. ;; GRADING -1 for each wrong answer, no partial credit for parts a-d Grading of part (e) is discussed above ;;;;;;;;;;;;; ;; QUESTION 2 ;;;;;;;;;;;;; ;; a) This question simply involved translating the expression n(n+1)/2 to scheme. In general, you don't need to put error checks into your code (i.e., make it bullet-proof) unless we ask. You should assume you're passed data in your domain. (define (sum n) (/ (* n (+ n 1)) 2)) or by expanding out the multiplication, also perfectly valid. (define (sum n) (/ (* n (+ n 1)) 2)) ;; GRADING -1 trivial error -2 big error (like swapping the order of the division) -3 any use of recursion Many people added "word" outside the return value. This doesn't change the answer; it's like adding zero to the return value. We allowed it for this exam, but it shows a little bit of confusion and will lose points in future exams. ;; b) This question asked if you could properly compose calls to sum-of-cubes correctly. The problem was based on the difference-between-dates case study. The idea is that we need to return the cubes of m through n inclusive (including m and n). So, if we subtract the cubes of 1 2 3 ... (m-1) m (m+1) ... (n-1) n ...from... 1 2 3 ... (m-1) ...it leaves... m (m+1) ... (n-1) n <-- the answer Be careful -- notice that we have to subtract the (m-1) term away. Many people missed this one. (define (sum-of-cubes-range m n) (- (sum-of-cubes n) (sum-of-cubes (- m 1)))) or you could subtract 1-m from 1-n and then add back in the mth term, i.e., subtract the cubes of 1 2 3 ... (m-1) m (m+1) ... (n-1) n ...from... 1 2 3 ... (m-1) m ...it leaves... (m+1) ... (n-1) n ...but we have to add back the m term m ...leaving... m (m+1) ... (n-1) n <-- the answer (define (sum-of-cubes-range m n) (+ (- (sum-of-cubes n) (sum-of-cubes m)) (cube m))) ;; GRADING -1 off-by-one error (subtracted m from n) -1 switching m and n -2 using all math instead of calling sum-of-cubes (but code must be correct) -3 for calling sum or using any recursion ;;;;;;;;;;;;; ;; QUESTION 3 ;;;;;;;;;;;;; ;; a) We were given middle, unend, triple, right and left. (______ '(abc def ghi jkl mno)) ==> def The only way to extract one of the words is to use middle. unend only cuts the end off but still leaves us with a sentence (-2)! We need to rotate the sentence to the right so that it'll line up for a call to middle. Thus the answer is: (middle (right Some also succeeded, albeit with some extra work (full credit) (middle (unend (right (middle (unend (unend (right ;; GRADING -0 missing right parens (we usually give free function-ending right parens) -1 trivial mistake -2 for (unend (unend (right -2 some code that shows they know HOW to compose but not WHAT to compose -2 for no open parenthesis, but it has to be exactly correct. -3 for really egregious errors -3 for not following directions (and including anything other than the functions we allowed) ;; b) (_____ 'fghij)) ==> highigh We need to remove f and j first (using unend), leaving "ghi" then triple it so that we can add at least three h's, leaving "ghighighi" then just remove the ends (using unend), leaving "highigh" ... done! (unend (triple (unend 'fghij))) Some also succeeded, albeit with some extra work (full credit) (unend (left (triple (right (unend 'fghij))))) (unend (right (triple (left (unend 'fghij))))) ;; GRADING similar to (a) ;;;;;;;;;;;;; ;; QUESTION 4 ;;;;;;;;;;;;; (define (logic1 a b c) (cond (a (if b #f #t)) (else c))) (define (logic2 a b c) (or (and a (not b)) c)) Hmm... are these the same or not? There are two ways to find out. The first is to create a truth-table of possible values for a, b and c and see if logic1 and logic2 are the same: a b c logic1 logic2 #f #f #f #f #f #f #f #t #t #t #f #t #f #f #f #f #t #t #t #t #t #f #f #t #t #t #f #t #t #t #t #t #f #f #f #t #t #t #f #t <-- difference! Thus, the answer is NO, they are DIFFERENT, and the value for A, B and C are all #t! Another way is to inspect the two functions carefully. In logic1, c is completely ignored if a is true. In logic2, because c is one of the arguments of the outermost "or", if c is true, the output is true (a,b are ignored). So, hmm, it seems a and c are special. To make logic1 ignore c, we have to set a=#t. To make logic2 true, we have to set c=#t and a,b will be ignored. So the question is whether we can set b so that logic1 returns #f, since we know logic2 will return #t. Turns out that if a is #t, logic1 simply returns "(not b)". Thus to make logic1 return #f b must be #t. Therefore a, b and c must all be true! ;; GRADING If you answered YES, you could get 2 points for answering the followup question correctly, which is (logic1 #t #f #f) ==> #t (see discussion above) If you answered NO but chose the wrong answer, you could also get 2 points.