CS3 SPRING 2000 Midterm Answers & Grading Notes (each answer prepared and graded by a different person) ---------------------------------------------------------------------- Question 1: GENERAL GRADING STANDARDS - every answer entry in this question is worth 1 point - in general, each answer entry must completely match the solution in order to be correct, except for the following exceptions : 1. A missing CLOSING parenthesis in an answer entry will be ignored. However, if the answer entry is missing an OPEN parenthesis, then the answer will be considered incorrect. The reason for this is that missing a closing parenthesis is just a careless mistake or counting error while missing an open parenthesis indicates a misunderstanding of programming concept. Example : If the correct answer to a question is (a b (c) ((d))), then (a b (c) ((d)) will be considered correct while a b (c) ((d)) will be considered incorrect. 2. Quoting errors will only be penalized by 0.5 points. 3. If the correct answer is a ERROR, students who indicate that the result is an error will be given full credit even they give incorrect explanation. (The reason is that we only require you to write the word "error" for the answer entry) PART A : L will return ( ((cal)) (bears) second-to () ) because you have defined L to be that list. Many students forgot one closing parenthesis on this answer by did not get penalized due to the exception noted above. PART B : (length L) is 4 since ( ((cal)) (bears) second-to () ) has 4 elements. PART C : (cdaar L) is equivalent to (cdr (car (car L))). The correct answer is (). Many students did not realize that (cdr '(cal)) is () and instead put down (al). Remember that cdr means to return the given list with the first element removed. In this case, the first element is cal. So removing cal from (cal) gives (). Part D : (bronze '() 5) gives you (() (* x y)) as result. Notice that the (* x y) is quoted in the body of the bronze function. Therefore, calling bronze with '() and 5 as arguments will simply evaluate to (list '() '(* x y)). PART E : (bronze #f (/ 1 (truncate 2/3))) will return an ERROR because (truncate 2/3) will return 0. Therefore, when the interpreter evaluates the second argument to bronze, it will try to divide 1 by 0 and hence an error results. Many students got this question wrong because they forgot that scheme evaluates a function's given arguments prior to executing the body of the function. PART F : (silver 'list '(list)) will return (list list). The silver function acts exactly like the cons function since (append '() list) will evaluate to just the given list itself. Therefore, (silver 'list '(list)) is the same as (cons 'list '(list)) and thus return (list list) as result. PART G : (silver cal (silver '() '())) will return (number-1 ()). The inner call (silver '() '()) will evaluate to (()). And since cal has been defined to be number-1, the outer silver function call with cons the word number-1 onto the front of (()), thus returning (number-1 ()). Many students got this question wrong because they forgot that cal is a previously defined variable and thus they thought that calling silver with cal unquoted with result in an error. PART H : (gold 'cal) will return an ERROR. The reason is that since the word list is used an a parameter name in the definition of gold, this parameter name has replaced the predefined list function in the body of the gold function. In other words, when (list list) is executed as the body of the gold function, the word list represents whatever argument you give to the gold function, rather than the predefined list function. Thus, when you call (gold 'cal), the body of the gold function will try to execute the literal word cal rather than the list function, which will result in an error. PART I : (gold 'list) will return an ERROR for the same reason as part H. Even though you are calling the gold function with 'list, you will still get an error because you are passing in a WORD rather than a FUNCTION (since the argument is 'list rather than list). To clarify : If you call (gold list) instead of (gold 'list), then you will get (#) as result instead of an error. PART J : '('these-were-hard) will return ('these-were-hard). This is because anything that is quoted is taken in literally, even if the object has another quote embedded inside it. '('these-were-hard) can be translated to (quote ('these-were-hard)). Thus, as result you will get the argument to the quote function, which is ('these-were-hard). Many students wrote (quote these-were-hard) as their answer. This is incorrect because (quote these-were-hard) is equivalent to 'these-were-hard rather than ('these-were-hard). ---------------------------------------------------------------------- Question 2a: Solutions: My solution was: (define (sum-ends L) (reverse (sum-firsts (reverse L))) ) (define (sum-firsts L) (cons (+ (car L) (cadr L)) (cddr L)) ) More common solutions were: (define (sum-ends L) (reverse (cons (+ (car (reverse L)) (cadr (reverse L)) ) (cddr (reverse L)) ) ) (define (sum-ends L) (append (reverse (cddr (reverse L))) (list (+ (car (reverse L)) (cadr (reverse L)) ) ) ) ) An interesting solution was to define last-two: (define (last-two L) (subseq L (- (length L) 2)) ) And the sum became: (+ (car (last-two L)) (cadr (last-two L)) ) Or to define second-to-last and last: (define (second-to-last L) (list-ref L (- (length L) 2)) ) (define (last L) (list-ref L (- (length L) 1)) ) And the sum became: (+ (last L) (second-to-last L) ) A few people split the problem into two with an if: (if (= (length L) 2) (list (+ (first L) (second L))) ;;Otherwise do one of the ways before ) This works, but is unnecessary, as the previous ways still work on lists of two elements. Many people did error checking, such as checking to make sure that the list contained at least two items, or making sure that the last two items were numbers. This was not required. Common Mistakes: - Some people did error checking incorrectly. As this was not required, no points were taken off. - On occasion, the (define (sum-ends L) was left off. This lost 1/2 point. - In order to remove the last two items in the list, some people did (remove car (remove car (reverse L))) or (remove second (remove first (reverse L))). Instead, use (cdr (cdr (reverse L))) or (rest (rest (reverse L))). This cost one point. - A more subtly flawed version of the above error was to do something like (remove (first (reverse L)) (reverse L)). This works on the example given, but not on (4 4 4 4), for example. It ends up removing more than you want. This cost one point. - Some people forgot to remove the last two elements. This cost one point. - Some people forgot the rest of the list entirely. This cost two points. - If * was used instead of +, 1/2 point was lost. - Forgetting open parentheses cost one point. - Although last was a defined function in semesters past, last was not defined this semester. Use without definition cost 1/2 point. - ' was not needed in this function. Incorrect use lost one point. - Some people attempted to use subseq to extract an element from the list. This cost one point. Subseq returns a list, and so canŐt be added. - Many people forgot to give the argument L to many functions. This cost a point. - Frequently, people did things similar to: (list (reverse (cddr (reverse L))) (+ (cadr (reverse L)) (car (reverse L)) ) ) There were several variations, but it boils down to the result having extra parentheses or having a dot. The given example has both. One point was subtracted for this kind of error. - Several people reversed the sum and the truncated list. One point was taken for this. - Commonly people gave values to subseq or list-ref that were off by one, such as (list-ref L (length L)) for last. This cost 1/2 point. - On occasion, this came up: (define (sum-ends L) (reverse L) (cons (+ (car L) (cadr L)) (cddr L)) (reverse L) ) Remember, when you have multiple expressions, all but the last are not useful. This is essentially the same as: (define (sum-ends L) (reverse L) ) This was one point off. - A few people tried (define reversed-L (reverse L)) and then used reversed-L in their functions. This does not work, as L is not defined except inside the procedure sum-ends. ---------------------------------------------------------------------- Question 2b: Any solution that worked AND did not use C, A, L, T, or + was accepted for full credit. The key line in the problem statement was "However, feel free to use any other list-creation functions you've written so far in the exam." Assuming you were solving problems in order, the ONLY function written so far was sum-ends (or possibly helper functions). This problem is unsolvable using only standard functions (I believe). The canonical solution was: (define (sum-four L) (sum-ends (sum-ends (sum-ends L))) ) The other common solution was: (define (sum-four L) (sum-ends (sum-ends (reverse (sum-ends L)))) ) Note: the reverse in the above solution was useless. Scoring: - Calling sum-ends four or two times cost a point. - As the point of the problem was to see if you could use functions defined elsewhere, one point was taken if you did not do so. - One point was taken if you used C, A, L, T, or + anywhere in your solution. - A number of people tried to start the function thus: (define (sum-four '(w x y z)) This is an error, and costs one point. Others did: (define (sum-four w x y z) The problem statement indicates the function should take one argument, not four. One point was taken for either of these errors. - Subseq returns a list. About 50% of wrong solutions were along the lines of: (define (sum-four x) (- (subseq x 0 1) (- (subseq x 1 2)) (- (subseq 2 3)) (- (subseq 3 4)) ) ) Subseq returns a list! You can not subtract lists. This is an error. The cost of this is one point. - If the given answer was close to correct, a minimum credit of 1/2 to 1 point was given. ---------------------------------------------------------------------- Question 2c: We are given 7*(x-2)*(x-2) Most common answer (* 7 x) (* x x) (- x 2) Other acceptable answers (* 7 x) (square x) (- x 2) (* 7 x) (expt x 2) (- x 2) ---------------------------------------------------------------------- Question 3: PART A (6 points) Grading scale: * 1 point for each expression * -1/2 for missing a quote * -1/2 for missing an open parenthesis a) : (cons '(why are) '(we here) ) ((why are) we here) OR : (cons '(why are) (list 'we 'here)) ((why are) we here) * I accepted all other "weird" solutions as long as they are correct such as : (cons '(why are) (cons 'we (list 'here))) : (cons '(why are) (append '(we) '(here))) : (cons '(why are) (append (list 'we) (list 'we))) b) : (append '(why are) '(we are)) (why are we here) OR : (append '(why are) (list 'we 'are)) (why are we here) * Some of you wrote it so in a "fancy" way that you forget to put a quote, costing you ­1/2 point : (append '(why are) (we) (are)) : (append '(why are) (list we) (list are)) * The following solutions are wrong (0 point) : (append '(why are) 'we 'are) : (list '(why are) '(we) '(are)) : (list (append '(why are)) 'we 'are) c) : (append '(why are) '((we here))) (why we (are here)) OR : (append '(why are) (list (list 'we 'here))) * This is a really "complicated answer", should I take some points off next time? You really show your understanding about cons, list, append, and quote here; but you should be careful, you may forget to put quotes. : (append '(why are) (list (cons 'we (list 'here)))) * Wrong solutions : (append '(why are) (cons 'we '(here))) : (list (append '(why are)) '(we here)) d) : (append '(why are) '(we here ())) (why are we here ()) OR : (append '(why are) '(we) '(here) '(())) * I took off 1/2 point if you wrote something like this : (append '(why are) '(we) '(here) '()) (why are we here) : (list (append '(why are) ) 'we 'here '()) ((why are) we here ()) * If you pass only one argument to the function append, it returns the same value as its argument. : (append '(why are)) (why are) e) and f) Your solution for part e) and part f) must be different. : (cons '(why are) '((we here)) ((why are) (we here)) OR : (list '(why are) '(we here)) ((why are) (we here)) * Some of you found a way to go around the restriction (good for you!). So, I also accepted the following solutions (ARE THEY REALLY DIFFERENT?) : (list '(why are) '(we here)) : (list (list 'why 'are) (list 'we 'here)) OR : (cons '(why are) '(we here)) : (cons '(why are) (list 'we 'here)) PART B (4 points) Grading scale a) (define (eight L) (car (cdddr (cdddr (cdr L))))) * * b) (define (eight L) (list-ref L 7)) * * c) (define (eight L) (first (subseq L 7 8))) * * * * OR (define (eight L) (first (reverse (subseq L 0 8)))) * Common errors: * Many of you use this function which is not defined in scheme: cadddddddr (-1/2 point) * Some of you still confuse the order of car and cdr when you write something like this: (cdddr (cdddr (cdar L))) . I just took off 1/2 point for that solution this time... * A lot of you wrote something like this (list-ref L 8) (list-ref L 6) You should know that an index of a list is counted from 0. * I also saw many of you write (define (eight L) (subseq L 7) ) I took off 1 point for that solution because * You can not assume that a list only has 8 elements * subseq always returns a list, therefore you need to call the first function again to take the eight element of the list. You also can not use CAR here because the question requires not to use C*R. * The following solutions are also correct: (define (eight L) (second (subseq L 6 8))) (define (eight L) (first (subseq (reverse L) (- (length L) 8)))) * However, I do not accept the following solutions (define (eight L) (first (reverse L))) ;; You cannot assume that a list only has 8 elements (define (eight L) ;; you cannot use the rest function. (car (rest (rest (rest (rest (rest (rest (rest L))))))))) ---------------------------------------------------------------------- Question 4a: (define (even-sum-a? x y) (even? (+ x y))) The idea is to check if the sum is even, or not odd. With two odd or two even numbers, the sum is always even. In all other cases it's odd. Points: 1-"even?" 1-"(+ x y)" ---------------------------------------------------------------------- Question 4b: (define (even-sum-b? x y) (or (and (odd? x) (odd? y)) (and (even? x) (even? y)))) Points: .5-"or" .5-"and" .5-"(odd? x) (odd? y)" .5-"(even? x) (even? y)" OR (define (even-sum-b? x y) (equal? (even? x) (even? y))) Points: 1-"equal?" .5-"(even? x)" .5-"(even? y)" Again, if both numbers are even, the result is even, so either of these possibilities should return a true as the result. The second function works because if both are even, #t=#t, and if both are odd, #f=#f. In all other cases, the result is #f. ---------------------------------------------------------------------- Question 4c: The solution we were looking for is (define (even-sum-c? x y) (if (even? x) (even? y) (odd? y) ) ) Similarly, you could have also had (if (odd? x) (odd? y) (even? y)) We also accepted a variety of other needlessly more complex solutions, such as (if (even? x) (if (even? y) (even? x) (odd? x)) (if (odd? y) (odd? x) (even? y)) ) Points were deducted for using any function other than if, even?, and odd?, for using #t or #f in your solution, or anything that always evaluates to one of either #t or #f (ie (even? 2)). Points were also deducted for any other scheme syntax errors. Partial credit was given to solutions that were close to correct. ---------------------------------------------------------------------- Question 4d: (define (even-sum-d? x y) (cond ((even? x) (even? y)) (else (odd? y))) OR (with equal correctness) (define (even-sum-d? x y) (cond ((even? x) (even? y)) ((odd? x) (odd? y))) Folks who got this question right understand that you can return a predicate as your return value. If we were to read this in english, it would say: "If x is even, return whether y is even too. If x is odd, return whether y is odd too" COMMENTS / GRADING STANDARDS i. Many people decided to bite the bullet and return #t/#f ii. Iffy answer... (cond ((even? x) (even? y)) (else (odd? x) (odd? y))) This actually works, because the else body has two expressions. The first is evaluated, ignored, and the last expression is correct, and equivalent to the second answer above. iii. Some wrong answers (cond ((even? x) (even? y) #t) ((odd? x) (odd? y) #t) (else #f)) and (cond ((even? x) (even? y) (even? x)) ((odd? x) (odd? y) (odd? x))) These don't work for the same reason answer (ii) works! The y tests are ignored and #t always returned. These people don't fully understand the syntax of cond, which is ( ) because they included more than two expressions in the field. Folks who did this only lost 1 point for the cond syntax. Folks who explicitly had #t/#f lost an additional point. iv. Some more wrong answers (cond ((even? x) (cond ((even? y) (even? x)) ((odd? y) (even? y)))) ((odd? x) (cond ((odd? y) (odd? x)) ((even? y) (odd? y))))) This got full credit because it works, but perhaps shouldn't have. The result expressions: (cond ((even? y) (even? x)) ((odd? y) (even? y)))) could have been re-written as simply (even? y). Make sure you understand that. Similarly for the (odd? y) part. v. Some folks did this (cond ((and (even? x) (even? y)) #t) ((and (odd? x) (odd? y)) #t) (else #f)) Which lost a point for and, and lost a point for #t. ---------------------------------------------------------------------- Question 5: 10 points total, 2 points each Grading standards: Forgetting quotes: -1 (total, not every time) One real mistake (trying (remove (not 1) L) to get rid of everything except the 1s in L): -1 Two real mistakes (trying (not 1) and forgetting to include L, as long as I could tell you were trying): -1.5 Three serious mistakes (like using recursion, getting it wrong, and getting the arguments to a function completely wrong): -2 Writing a solution for a "not in my power...yet!" or writing that when there was a solution: -2 1) (list-ref L (truncate (/ (length L) 2))) or (list-ref L (- (/ (length L) 2) .5)) or (list-ref L (/ (- (length L) 1) 2)) or (list-ref L (- (/ (+ 1 (length L)) 2) 1)) or (car (subseq L (truncate (/ (length L) 2)) (+ 1 (truncate (/ (length L) 2))))) or something like that 2) not in my power...yet! 3) (remove 'k (remove 'q (remove 'j L))) or (bad form, lots of room for error, and way too much writing) (cond ((member 'k L) (remove 'k (remove 'q (remove 'j L)))) ((member 'q L) (remove 'q (remove 'j L))) ((member 'j L) (remove 'j L)) (else L)) 4) (length (remove 'a L)) or (+ (count 'k L) (count 'j L) (count 'q L)) or (- (length L) (count 'a L)) or (- (length L) (- (length L) (length (remove 'k (remove 'j (remove 'q L)))))) 5) not in my power...yet!