diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/61a-pages/Volume2 | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/61a-pages/Volume2')
24 files changed, 4908 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/CS 61A Course Reader, Volume 2.html b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/CS 61A Course Reader, Volume 2.html new file mode 100644 index 0000000..56f5a05 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/CS 61A Course Reader, Volume 2.html @@ -0,0 +1,154 @@ +<html><head> +<meta http-equiv="content-type" content="text/html; charset=UTF-8"><title>CS 61A Course Reader, Volume 2</title><style type="text/css">@namespace url(http://www.w3.org/1999/xhtml); +@font-face { + font-family: 'EasyRead2'; + font-style: normal; + font-weight: 400; + src: local('EasyRead2'), url(https://cdn.rawgit.com/PullJosh/files/gh-pages/Arial-LargePeriod2.woff) format('woff'); +}input[type="text"], input[type="textarea"], textarea { + font-family: "EasyRead2" !important; + }</style></head> +<body> + +<center> +<h1> CS61A: Structure and Interpretation of Computer Programs </h1> +<h3> Course Reader, Volume 2: Reference Documents </h3> +</center> + +<p><b>These documents are here for online reference! Please do not print +these on the printers in Berkeley computer labs. Lab printers are for your +homework and project solutions, not for reference documents. Thank you.</b> + +</p><p>For many years I resisted the trend to putting course materials online, +but I've been convinced because of the increasing numbers of people who +aren't at Berkeley but use the +<a href="http://wla.berkeley.edu/main.php?course=cs61a">online lectures</a> +to study SICP. Welcome, visitors! + +</p><ul> +<li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/OOP/aboveline.pdf"> +Object-Oriented Programming: Above the Line View</a> +</li><li> <a href="OOP/ref-man.pdf"> +Reference Manual for the OOP Language</a> +</li><li><a href="OOP/belowline.pdf"> +Object-Oriented Programming: Below the Line View</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/gnuemacs.pdf"> +Highlights of GNU Emacs</a><sup>*</sup> +</li><li> <a href="quick.pdf"> +Emacs Quick Reference Guide</a><sup>*</sup> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/exit.pdf"> +Exit Information (Read at end of semester!)</a> +</li><li><a href="Therac-25.pdf"> +An Investigation of the Therac-25 Accidents</a><sup>**</sup> +</li><li><a href="r5rs.pdf"> +Revised<sup>5</sup> Report on Scheme</a><sup>***</sup><br /> +(the last <i>real</i> version of Scheme before its hostile takeover +by industrial programmers) +</li><li><a href="mapreduce-osdi04.pdf"> +MapReduce: Simplified Data Processing on Large Clusters</a><sup>****</sup> +</li><li>Sample Exams: +<ul> +<li><b>Please read this:</b> + +<p>These exams are made up of actual past exam questions, but reorganized to +make each sample more comprehensive and to choose the best possible questions. +Some of the exams are a little longer (by one question) than actual exams, but +they're in the right ballpark. + +</p><p>Since the questions within a sample are taken from different semesters, +don't try to compare the number of points between problems. The solutions +include scoring information only to give you an idea of how part credit is +awarded within each problem. + +</p></li><li>Midterm 1 +<ul> +<li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm1/mt1-1.pdf"> +Sample exam 1</a> +</li><li><a href="Midterm1/mt1-1.soln.txt"> +Solutions to sample exam 1</a> +</li><li><a href="Midterm1/mt1-2.pdf"> +Sample exam 2</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm1/mt1-2.soln.txt"> +Solutions to sample exam 2</a> +</li><li><a href="Midterm1/mt1-3.pdf"> +Sample exam 3</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm1/mt1-3.soln.txt"> +Solutions to sample exam 3</a> +</li></ul> +</li><li>Midterm 2 +<ul> +<li><a href="Midterm2/mt2-1.pdf"> +Sample exam 1</a> +</li><li><a href="Midterm2/mt2-1.soln.txt"> +Solutions to sample exam 1</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm2/mt2-2.pdf"> +Sample exam 2</a> +</li><li><a href="Midterm2/mt2-2.soln.txt"> +Solutions to sample exam 2</a> +</li><li><a href="Midterm2/mt2-3.pdf"> +Sample exam 3</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm2/mt2-3.soln.txt"> +Solutions to sample exam 3</a> +</li></ul> +</li><li>Midterm 3 +<ul> +<li><a href="Midterm3/mt3-1.pdf"> +Sample exam 1</a> +</li><li><a href="Midterm3/mt3-1.soln.txt"> +Solutions to sample exam 1</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm3/mt3-2.pdf"> +Sample exam 2</a> +</li><li><a href="Midterm3/mt3-2.soln.txt"> +Solutions to sample exam 2</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Midterm3/mt3-3.pdf"> +Sample exam 3</a> +</li><li><a href="Midterm3/mt3-3.soln.txt"> +Solutions to sample exam 3</a> +</li></ul> +</li><li>Final exam +<ul> +<li><a href="Final/f-1.pdf"> +Sample exam 1</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Final/f-1.soln.txt"> +Solutions to sample exam 1</a> +</li><li><a href="Final/f-2.pdf"> +Sample exam 2</a> +</li><li><a href="Final/f-2.soln.txt"> +Solutions to sample exam 2</a> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/Final/f-3.pdf"> +Sample exam 3</a> +</li><li><a href="Final/f-3.soln.txt"> +Solutions to sample exam 3</a> +</li></ul> +</li></ul> +</li><li><a href="mapreduce-osdi04.pdf"> +Mapreduce: Simplified Data Processing on Large Clusters</a><sup>****</sup> +</li><li><a href="https://people.eecs.berkeley.edu/~bh/61a-pages/Volume2/notes.pdf"> +Lecture Notes</a> +</li><li><a href="sicp-errata.txt"> +SICP Errata</a><sup>*****</sup> +</li><li><a href="word.txt"> +Berkeley Word/Sentence Functions</a> +</li><li>Ergonomic Information (external links): +<ul> +<li><a href="https://www.uhs.umich.edu/computerergonomics"> +Computer Workstation Ergonomics (UMich)</a> +</li><li><a href="https://www.ors.od.nih.gov/sr/dohs/HealthAndWellness/Ergonomics/Pages/ergonomics_home.aspx"> +Ergonomics (NIH DOHS)</a> +</li></ul> +</li></ul> + +<p> +*: Prof. Paul Hilfinger, UCB EECS<br> +**: Nancy G. Leveson, Clark S. Turner. IEEE <cite>Computer</cite>, July 1993<br> +***: Richard Kelsey, William Clinger, Jonathan Rees (Editors), et al., 1998<br> +****: Jeffrey Dean, Sanjay Ghemawat, Google, Inc., OSDI 2004<br> +*****: Harold Abelson, Gerald Jay Sussman, Julie Sussman, 1999 +</p><p> +</p><p> +</p><p> +</p><p><a href="../Volume1/CS 61A Course Reader, Volume 1.html">Volume 1</a> +</p><p><a href="../../61a-pages">Back to class web page</a> + + +</p></body></html> diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-1.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-1.pdf new file mode 100644 index 0000000..65ea079 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-1.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-2.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-2.pdf new file mode 100644 index 0000000..d5d8ddb --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-2.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-2.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-2.soln.txt new file mode 100644 index 0000000..4f1a8a1 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-2.soln.txt @@ -0,0 +1,540 @@ +CS 61A Solutions to sample final exam #2 + +1. HOFs in 21 project + +A higher order procedure is one that uses procedures as data -- either as +arguments or as its return value. Many people forgot about the latter. + +BEST-TOTAL takes a hand (a sentence) as argument and returns a number. +No procedures; not higher order. + +STOP-AT-17 takes a hand (a sentence) and a card (a word) as arguments, +returning #T or #F. No procedures; not higher order. + +PLAY-N takes a strategy (which is a procedure!) and a number as arguments, +returning a score. It's higher order. + +STOP-AT takes a number as argument, returning a strategy -- a procedure. +So it's higher order. + +MAJORITY takes three strategies as arguments and returns a strategy. +Clearly higher order! + + +Scoring: 2 points if correct; 1 point if all but one correct (usually +leaving out STOP-AT). + + +2. Foo and baz. + +(foo 3) ==> (if 3 (foo #f) 5) + ==> (foo #f) + ==> (if #f (foo #f) 5) + ==> 5 + +(baz 3) ==> (and 3 (baz #f) 5) + ==> (and (baz #f) 5) ; since 3 is true + ==> (and (and #f (baz #f) 5) 5) + ==> (and #f 5) ; inner AND is false + ==> #f + +Scoring: 1 point each. + + +3. Iterative and recursive. + +FOO is iterative; BAZ is recursive. + +In FOO, when IF decides to evaluate (foo #f), it already knows that whatever +the answer from (foo #f) is will be the answer to the entire problem. + +In BAZ, after the (baz #f) returns, AND must check whether the answer is +true or false. If false (as, in fact, it is), then indeed the answer to +(baz #f) is also the answer to (baz 3). But AND didn't know that until the +recursive call is complete! If (baz #f) had been true, the answer would +have been 5. + +A good one-sentence answer: "An iterative process is one in which +the caller has no more work to do once the recursive callee returns." + +Many people quoted sentences from the book, often the one about "deferred +operations"; we accepted these if it sounded as if you might have some idea +what it actually meant. + +Some people quoted a sentence about how something "depends on the return +value" but mostly these answers were wrong: the answer to the overall +problem does depend, in both cases, on the answer to the recursive call. +The question is whether it also depends on anything else! + +Worst of all was "FOO is iterative because IF is a special form." +Sorry -- AND is a special form, too! + +Scoring: 2 points if you had FOO iterative and BAZ recursive, with a +convincing sentence. 1 point if you had FOO iterative and BAZ recursive. +(If you had FOO recursive and/or BAZ iterative, we didn't even read your +sentence.) + + +4. How are the pairs connected? + +We know that A's box and pointer diagram looks like this: + +A --> [1 . -]---> [2 . -]---> [ | . -]---> [6 . /] + | + V + [3 . -]---> [4 . -]---> [5 . /] + +We also know that (CDDR B) is the same pair as (CADDR A), which is the pair +whose car is 3. Therefore the list (3 4 5) is shared between A and B, so +the diagram is + +A --> [1 . -]---> [2 . -]---> [ | . -]---> [6 . /] + | + V + B --> [1 . -]---> [2 . -]---> [3 . -]---> [4 . -]---> [5 . /] + +We also know that (CADDR C) is *not* the same pair as (CADDR A), so the list +C must have its own distinct pair with 3 in the car. On the other hand, +(CDADDR C) *is* the same as (CDDDR B), so the pairs with 4 and 5 in the cars +are shared between C and the other lists: + +A --> [1 . -]---> [2 . -]---> [ | . -]---> [6 . /] + | + V + B --> [1 . -]---> [2 . -]---> [3 . -]---> [4 . -]---> [5 . /] + ^ + / + [3 . -]--/ + ^ + | +C --> [1 . -]---> [2 . -]---> [ | . -]---> [6 . /] + +(Actually, we don't know whether or not A and C share the pair whose car is +6. But this will turn out not to affect the solution.) + +Now we make two changes to the box and pointer diagram, changing one of the +threes to a seven, and changing the four to an eight: + +A --> [1 . -]---> [2 . -]---> [ | . -]---> [6 . /] + | + V + B --> [1 . -]---> [2 . -]---> [7 . -]---> [8 . -]---> [5 . /] + ^ + / + [3 . -]--/ + ^ + | +C --> [1 . -]---> [2 . -]---> [ | . -]---> [6 . /] + +We can read the results directly from the diagram: + +B is (1 2 7 8 5) +C is (1 2 (3 8 5) 6) + +Scoring: 1 point each. + + +5. OOP to normal Scheme + +(define (make-echo saved) + (let ((count 0)) + (lambda (message) + (cond ((eq? message 'count) count) + ((eq? message 'saved) saved) + (else (set! count (+ count 1)) + (let ((result saved)) + (set! saved message) + result)))))) + +The code for the ELSE clause is exactly the code for the default-method +in the OOP class definition! We didn't understand why so many people +invented much more complicated ways to do it -- or, worse, incorrect ways. + +Scoring: +3 correct +2 has the idea (at least a dispatch procedure inside the let) +1 has an idea +0 other + +Most people did okay on this, but a fairly frequent one-point answer had the +LET (for COUNT) inside the LAMBDA instead of outside. This means you missed +the whole idea about local state variables. + +A noteworthy zero-point solution tried to avoid the problem that the inner +LET solves this way: + + (else (set! count (+ count 1)) + (display saved) ; wrong wrong wrong! + (set! saved message)) + +By now everyone should understand that procedures return values, and that +printing isn't the same as returning, because it doesn't allow for +composition of functions, the most important programming technique you will +ever learn. + + +6. mystery stream + +The stream is made by sticking a 1 in front of an interleave of the integers +with something: + +1 1 ___ 2 ___ 3 ___ 4 ___ 5 ___ 6 ___ 7 ___ 8 ___ 9 ___ 10 + +Then you just fill in the blanks with the elements of MYSTERY, including all +of them -- the initial 1, the integers, and the underlined ones: + +1 1 _1_ 2 _1_ 3 _1_ 4 _2_ 5 _1_ 6 _3_ 7 _1_ 8 _4_ 9 _2_ 10 + + +Scoring: 3 points for the above solution. 2 points for small errors (such +as one number missing); there weren't many of those. 1 point for the +following wrong sequence: + + 1 1 1 2 1 3 2 4 1 5 3 6 2 7 4 8 1 9 5 10 + +which is reached by forgetting about the initial 1 and trying to create +(interleave mystery integers) instead, making the initial 1 part of the +interleaved values. + + +7. Infix in metacircular evaluator. + +This was an interesting question because the most aesthetically pleasing +solution isn't the easiest solution. + +This problem asks you to change the notation of expressions, not their +meaning. EVAL is about expressions; APPLY is about what it means to call a +function. So the right place for this change is in EVAL, changing the COND +clause for procedure calls to this: + + ((application? exp) + (let ((left (eval (operator exp) env))) + (if (or (compound-procedure? left) + (primitive-procedure? left)) + (apply left (list-of-values (operands exp) env)) + (if (= (length exp) 3) + (apply (eval (cadr exp) env) + (list left (eval (caddr exp) env))) + (error "Applying non-procedure" left))))) + +It's important to do the evaluating of subexpressions exactly right: only +once each (just in case the expression involves side effects), but before +testing for procedureness (because it's the value that's a procedure -- or a +number, if you're testing for numbers -- not the expression). That's why I +had to use a LET to save the result of evaluating the first subexpression. + +This is an important point, missed by many students. The example in the +exam was just (2 + 3), but it should also work to say (x + 3), or +((2 * 5) + 3), and in those cases the first subexpression is not itself +a number. The *value* of the expression is a number. Similarly, if you're +looking at the second subexpression, the problem could be + (2 (car (list + - *)) 3) +in which the second subexpression has an arithmetic operator as its value. + +All of that is avoided if you make the change in APPLY, where you take apart +the arguments you're given and rearrange them if needed. But it's not an +aesthetically pleasing solution, partly because applying a procedure to +arguments is a semantic operation that shouldn't know anything about the +shape of the expression the user typed, and partly because it means +disassembling an argument called "arguments" to look for a procedure in it, +and using the argument called "procedure" as an argument. + +Another solution would be to have an intermediate step between EVAL and APPLY, +like this: + +(define (eval exp env) + (cond ... + ((application? exp) (check-infix (list-of-values exp env))) + ...)) + +(define (check-infix values) + (if (and (not (meta-procedure? (car values))) + (= (length values) 3) + (meta-procedure? (cadr values))) + (apply (cadr values) (cons (car values) (cddr values))) + (apply (car values) (cdr values)))) + +(define (meta-procedure? thing) + (or (primitive-procedure? thing) + (compound-procedure? thing))) + +Some solutions treated the problem as one of syntactic rewriting, like +changing a COND to an IF or vice versa. This can work, except for the fact +that you have to partly evaluate the expression in order to know whether or +not to do the rewriting, and then you'll end up evaluating something twice. + +Another solution, very clever and elegant in its intent, has the same +problem of double evaluation: rewriting the OPERATOR and OPERANDS selectors, +similar in spirit to the way the selectors for a DEFINE expression recognize +the implicit-lambda special case. But in the DEFINE situation, we can tell +just from the notation -- the syntax -- whether or not an implicit lambda is +involved. In the case of infix arithmetic we're not sure until we've +evaluated some subexpressions. + +Other solutions reordered the expression by mutation. We didn't take off +for that if it was otherwise correct, but you should try not to develop the +habit of mutating data structures that you get as arguments unless that's +specifically in the "contract" with the caller of your procedure. That same +data structure might be shared with some other purpose. + +The intent of the problem was that *any* two-argument procedure should be +usable in infix notation. The problem statement says "[i]f a compound +expression has three subexpressions, of which the second is a procedure but +the first isn't..." But since the problem statement did also mention "infix +arithmetic," we accepted solutions that work only for the specific operator +symbols +, -, *, and so on. However, such solutions aren't very Schemely, +since the binding of those symbols to arithmetic functions isn't guaranteed. +A Scheme program could say + + (let ((plus +) (+ word)) ...) + +and then the value of (+ 3 4) would be 34! + +Note how my solution checks for a procedure. Strictly speaking, you can't +use PROCEDURE? to check, because that's a Scheme primitive that checks for +whether something is a procedure in the underlying Scheme, not a procedure +in the metacircular Scheme. But we didn't take off for this subtle error. + + +Scoring: + +4 correct + +3 subexpression(s) evaluated twice + failure to check that the first subexpression isn't a procedure + [consider the case (map - '(4 5 6)) which isn't infix!] + +2 testing unevaluated subexpressions for being procedures or numbers + +1 no evaluation at all + infix works but prefix doesn't + +0 references to line-obj or other such Logo interpreter structures + +Of course not every error is listed above, but these are the common ones. + + +8. Logic programming + +(a) Less + +The solution we were expecting was this: + +(rule (less () (a . ?y))) ; 0 < anything positive + +(rule (less (a . ?x) (a . ?y)) ; if x < y then x+1 < y+1 + (less ?x ?y)) + +Several variants were also okay. The first rule above could be replaced by + +(rule (less () ?x) + (not (same ?x ()))) + +but not just by + +(rule (less () ?x)) ; wrong! + +because that would allow the case 0 < 0, and not by + +(rule (less () (?x))) ; wrong! + +because that only allows for 0 < 1, not for other larger numbers. But +having a 0 < 1 rule is okay if you also include a rule + +(rule (less ?x (a . ?y)) ; if x < y then x < y+1 + (less ?x ?y)) + +But it's quite wrong to have a rule, as many papers did, that if x < y +then x+1 < y. That's not true! + +(Some combinations of these rules would lead to the query system giving +the same answer more than once, which is unaesthetic. The first set of +rules above avoid that.) + +Another approach would use PLUS, which you're given: + +(rule (less ?x ?y) + (plus ?x (a . ?z) ?y)) + +This says that x < y if adding some positive number to x gives y. This is +elegant because a single rule handles all cases. + + +(b) Divide + +Only one rule is needed: + +(rule (divide ?dividend ?divisor ?quotient ?remainder) + (and (times ?divisor ?quotient ?x) + (plus ?x ?remainder ?dividend) + (less ?remainder ?divisor))) + +The third clause is needed to prevent solutions such as 12/4 = 1 remainder 8. + +Many people included a lot of base case rules for dividing zero by things, +dividing things by zero, and so on -- or wrote the rules to exclude zero by +calling the divisor (a . ?foo). None of this is necessary; there won't be +any successful matches of this rule when the divisor is zero. (This is +easy to prove: the remainder would have to be less than zero!) + +The reason no base case is needed is that this is not a recursive rule; +there is no reference to DIVIDE in the conditions of the rule. There is +still some recursion going on, but it's hidden inside the PLUS and TIMES +rules. + +Scoring: Each half was worth 2 points if correct, 1 point for a solution that +has the general idea but with details wrong. (A common mistake was to think +that the remainder has to be less than the quotient, or less than the dividend.) + +No credit for composition of functions: + + (plus (times ?divisor ?quotient) ?remainder ?dividend) ; WRONG WRONG WRONG!!! + + +9. Environment diagram + +In the diagram there are three frames: + +G: x=3, y=4, foo=P2 [see below] (the global frame) +E1: x=7, extends G +E2: y=10, extends E1 + +and two procedures: + +P1: parameter x, body (lambda (y) (+ x y)), created in G +P2: parameter y, body (+ x y), created in E1 + +When we define FOO, Scheme evaluates the expression + + ( (lambda (x) (lambda (y) (+ x y))) + (+ x y) ) + +The value of the first subexpression is procedure P1, created in the +global environment (obviously, since it's the only one we have so far). +The value of the second subexpression is 7, computed using the global +values of X and Y. + +We invoke P1, creating environment E1, in which P1's parameter X is bound to +the actual argument value 7. In that new environment we evaluate the body +of P1, which is another lambda expression, creating P2. + +Then DEFINE binds FOO to that result, P2, in the global environment. + +When we evaluate the expression (foo 10), environment E2 is created. FOO's +parameter Y is bound to the argument value 10, in the new frame. Then we +evaluate the body of P2, (+ x y), using the values in E2: x=7 (from E1), +y=10. So the answer is 17. + + +Scoring: 1 point for the answer 17. For the diagram, 3 points minus the +number of mistakes. In counting mistakes we looked for three frames, +two procedures, and five arrows (two arrows extending environments, +two arrows from procedures to environments, and the arrow binding FOO). + +There were too many rearrangement errors to classify, but one common error +that's worth mention was to say that in E1, X is bound to x+y. By the time +E1 is created, we no longer know where the argument value 7 came from; +that's what it means to say that Scheme uses applicative order. + + +10. Locate. + +The most elegant solution, I think, is this: + +(define (locate value struct) + (define (help struct fn) + (cond ((equal? value struct) fn) + ((pair? struct) + (or (help (car struct) (compose car fn)) + (help (cdr struct) (compose cdr fn)))) + (else #f))) + (help struct (lambda (x) x))) + +This is a case in which an iteration-like style, with a helper procedure +with an extra argument, makes things simpler instead of more complicated. +(It's not really iterative, of course, since there's a tree recursion, +but the second recursion, for the cdr, *is* iterative.) + +Here's a more straightforward solution: + +(define (locate value struct) + (cond ((equal? value struct) (lambda (x) x)) + ((pair? struct) + (let ((left (locate value (car struct)))) + (if left + (compose left car) + (let ((right (locate value (cdr struct)))) + (if right + (compose right cdr) + #f))))) + (else #f))) + +Note that for both the car and the cdr you have to check whether the +recursive call actually returned a procedure, rather than #F, before you +try to compose the procedure with something. + +Instead of using COMPOSE you could equivalently use lambda expressions: + (lambda (x) (left (car x))) + +Notice, by the way, that the iterative-style solution does the composing +backwards from the recursive-style solution; this is analogous to the list +reversal that plagues iterative solutions to list-building problems. + +One point that many students missed is that the problem says "If the value +is not found in the structure, LOCATE should return #F" -- not a procedure +that returns #F! So you can't say + +(define (locate value struct) + (lambda (other-struct) ...)) ; wrong + +Another commonly missed point is that the problem does *not* say the values +have to be atomic. (locate '(a b) '(x y (a b) z)) should work, returning +the procedure caddr. In particular, this means that solutions that flatten +the structure into a simple sequence of atoms, although clever in a way, +miss the point and aren't satisfactory. + +Even worse were the solutions that assume the values are numbers, just +because the given example had numbers. A relatively mild version of that +was to use = for equality checking; much worse was to use list-ref to look +for the desired element. + +A couple of students used AMB in their solutions. Although we had in mind +a solution using standard Scheme, we would have allowed this, because it's +such an appropriate idea -- the problem involves backtracking, so a +nondeterministic solution makes sense. But actually getting it right is +tricky, and nobody managed it: + +(define (locate value struct) + (define (locate1) + (define (help struct fn) + (cond ((equal? value struct) fn) + (else (require (pair? struct)) + (let ((cxr (amb car cdr))) + (help (cxr struct) (compose cxr fn)))))) + (help struct (lambda (x) x))) + (amb (locate1) #f)) + +That LOCATE1 subprocedure is required because in case of failure, the +natural response of the nondeterministic evaluator is to print a message +saying no more values were found, but we want it to return #F to some +calling procedure. + +Many students made the program much more complicated than necessary, with +special cases for (car struct), (cadr struct), etc. Partly this is because +students don't believe in leaf nodes of trees, and partly it's because +some students found a somewhat similar problem, called SELECT, in a previous +exam in the course reader. But SELECT really did require complications, +because the first element of a sublist had a special meaning in that problem. +Here the elements are treated uniformly. + + +Scoring: + +4 correct +3 small errors (typical: only works for atoms, only works if no #F in a list, + returns (lambda (x) #f) instead of #f) +2 has the idea (domain and range correct, uses tree recursion) but + more serious errors +1 not tree recursive (typical: if the car is a list, and doesn't have the + value, then the cdr isn't checked) +0 incoherent diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-3.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-3.soln.txt new file mode 100644 index 0000000..0c4cc82 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Final/f-3.soln.txt @@ -0,0 +1,1125 @@ +CS 61A Solutions to sample final exam #3 + +1. Domain and range + +The domain of a procedure is the TYPE of thing(s) it accepts as argument(s). +The range is the TYPE of thing it returns. So we wanted types as the answers +to this question. That's generally what you gave for the domain, but for the +range, several people instead gave explanations of the purpose of the +procedure, e.g., "Range: the children of the tree node." + +(a) CHILDREN + +CHILDREN takes one argument, a Tree (which is the same as a node). +It returns a forest, which is a list of Trees. So: + + Domain: TREE or NODE + Range: FOREST or LIST OF TREES or just LIST + +Most people got this one. + +(b) OWNER + +OWNER takes one argument, a THING object. It returns the *name of* the +person who owns the thing (not the person, not the name of the thing). +A name is a word, not an object! So: + + Domain: OBJECT or THING OBJECT or THING INSTANCE + Range: WORD + +We also accepted NAME for the range, although that isn't really a type. +The most common wrong answer for the range was PERSON; that's a kind of +object, not a word. A fairly common wrong answer for the domain was CLASS; +the procedure takes a particular thing as its argument, not the class of all +things. Another common wrong answer was PROCEDURE; it's true that we use +procedures to represent objects, but not every procedure is an object, and +not every procedure can be used as the argument to OWNER. + +(c) SET-CDR! + +SET-CDR! takes two arguments; the first must be a pair, and the second can be +of any type. Its return value is unspecified, since it is used for its effect +rather than for its return value, so we accepted anything for the range in +this part. + + Domain: PAIR and ANYTHING (you had to say both). + Range: UNSPECIFIED (but we accepted anything). + +We didn't accept LIST for the domain; there is no requirement that the first +argument to SET-CDR! be a pair whose cdr is a list (which is what it means for +a pair to be a list). Also, the LIST domain would include the empty list, +which can't be used as the first argument to SET-CDR!. + +Scoring: One point each, all or nothing. + + +2. Data abstraction + +The argument is a LIST of RATIONALs. For the list itself, the appropriate +selectors are CAR and CDR. (Constructors for lists include CONS, LIST, and +APPEND, but in this problem we are not constructing a list!) For a rational +number, the constructor is MAKE-RAT and the selectors are NUMER and DENOM. +So the corrected version is + +(define (ratprod lst) + (define (helper lst n d) + (if (null? lst) + (MAKE-RAT n d) + (helper (CDR lst) (* n (NUMER (CAR lst)) (* d (DENOM (CAR lst))))))) + (helper lst 1 1)) + +The call to CDR doesn't change because it is selecting part of a list, not +part of a single rational number. The calls to CAAR and CDAR do change, +as shown above; they both select the first element of the list (CAR), and +each then selects one piece of a rational number (NUMER or DENOM). + +Scoring: -1 point per error, either a required change not made or something +changed that shouldn't have been. But 0 points if no correct change was +made at all (e.g., if the question was left blank). + + +3. Order of growth + +(a) + +(define (two-to-the n) + (if (zero? n) + 1 + (let ((prev (two-to-the (- n 1)))) + (* prev 2) ))) + +Each call to this procedure does three constant-time operations (ZERO?, -, +and *) in addition to making one recursive call. So there are N recursive +calls, each of which takes constant time. Therefore, this procedure takes +time Theta(N). + +(b) + +(define (two-to-the n) + (if (zero? n) + 1 + (let ((prev (two-to-the (- n 1)))) + (+ prev prev) ))) + +The only difference here is (+ PREV PREV) instead of (* PREV 2). This +is still a single, constant-time arithmetic operation, although both operands +are the variable PREV rather than including the explicit number 2. But +finding the value of a variable is also constant time, so this doesn't affect +the program's running time, which is still Theta(N). + +(c) + +(define (two-to-the n) + (if (zero? n) + 1 + (+ (two-to-the (- n 1)) + (two-to-the (- n 1)) ))) + +In this version, each call to TWO-TO-THE gives rise to *two* recursive +calls. So, for example, (two-to-the 5) calls (two-to-the 4) twice; each +of those makes two calls, for a total of four calls of (two-to-the 3). +Similarly, there are eight (two-to-the 2) calls and 16 of (two-to-the 1). +Increasing N by 1 doubles the total number of recursive calls, so the +running time for this procedure is exponential, Theta(2^N). + +The most common error was to think that the last version was Theta(N^2). + +Scoring: One point each. + + +4. Functions of functions. + +The point of this question is to illustrate some of the ways in which +functions can be manipulated on their own, without explicit reference to +the arguments of the functions. You've seen COMPOSE before, in lecture; +the other two tools given here are similar in spirit. + +One way to think about these questions would be to try writing the +desired procedure without using COMPOSE, SPECIALIZE, or SWAP-ARGS, and +then think about how you did it. + +[a] INITIALS + +(define (initials sent) + (every first sent)) + +So INITIALS is a specialized version of EVERY, in which the first +(procedure) argument is FIRST. Thus we have the answer: + +(define initials (specialize every first)) + + +[b] POSITIVE? + +(define (positive num) + (> num 0)) + +This is a specialization of >, in which the *second* argument is held +constant (zero), not the first argument as in INITIALS. So SPECIALIZE +won't quite do the job by itself. One solution would be to use < +instead of >: + +(define (positive num) + (< 0 num)) + +(define positive (specialize < 0)) + +but that wasn't one of the choices. Instead we use SWAP-ARGS to get +the arguments in the right order: + +(define positive (specialize (swap-args >) 0)) + + +[c] LEAF? + +(define (leaf? node) + (null? (children node)) + +This is a composition of functions: + +(define leaf? (compose null? children)) + + +Scoring: One point each. + + +5. Mystery function on Trees + +(define (mystery tree) + (if (null? (children tree)) + (make-tree (datum tree) '()) + (make-tree (+ (datum tree) 100) + (map mystery (cdr (children tree)))))) + +This function says: If the node is a leaf, return a leaf node with the +same datum. (This is actually unnecessarily complicated; it could have +just returned the argument TREE itself, since the node it constructs has +the same datum and the same (empty) children.) If the node isn't a leaf, +add 100 to its datum, and recursively apply the same function to its +children, but omit the first child (because of the CDR call). + +In the given tree, the root node (datum 1) has three children, so we add +100 to its datum (giving 101), we omit the subtree headed by the node with +datum 2, and we recursively process nodes 3 and 4. + +Node 3 (I'm using this as an abbreviation for "the node with datum 3" and +similarly for the other nodes) has two children, so we add 100 to its +datum, omit the first child (6), and recursively process the other child +(node 7). + +Node 7 has no children, so we just return a leaf with datum 7. + +Node 4 has one child. So we add 100 to its datum, omit its first (only) +child 8, and recursively process its other children -- but there aren't +any, so the node with datum 104 will be a leaf node in the resulting tree. + +Omitting a node doesn't just mean omitting the datum of that node; we +never look at its children either. So we don't have to think about nodes +5, 9, and 10. + +Don't forget that this function builds a new tree! It doesn't mutate the +argument tree. In particular, one common wrong answer was to return a +tree with 10 nodes, just like the argument tree, but with 100 added to +some of the data. The correct answer is a tree with only the four nodes +mentioned earlier as part of the result: + + 101 + / \ + 103 104 + | + 7 + +Another too-common mistake was to draw a tree in which some nodes have +lists as the datum. For example, the child of the 103 node was shown as +having (7) as its datum, or the 104 node had a child with the empty list +as its datum. These errors, I think, come from not respecting the data +abstraction, but instead trying to translate the tree selectors and +constructor into operations on pairs. As you can see from the explanation +above, there is no need to think about how tree nodes are represented! The +only pair operation used is the CDR in the procedure, and that's because +(CHILDREN TREE) returns a forest -- a list of trees -- rather than a single +tree node. + +Several people thought that a Scheme error would result from the expression + + (map mystery (cdr (children tree))) + +when it is applied to the 4 node, which has only one child, because in this +case the expression is equivalent to + + (map mystery '()) + +But there's nothing wrong with this -- MAP is happy to take the empty list +as its second argument, in which case it returns the empty list without +ever calling MYSTERY. Empty lists are legitimate lists! + + +Scoring: + +5 Correct. + +4 Correct except that instead of 101, 103, and 104, the values in those + nodes are computed by some different arithmetic; most commonly these + nodes have the data 101, 301, and 401. Node 7 must be correct. + +3 Right shape, but one incorrect datum (most often 107 instead of 7). + +2 The four correct nodes plus one or two extras, including the case of + "error" as a child of node 104. + +2 The solution obtained by ignoring the CDR in the procedure: 10 nodes + in the same shape as the original, but with 1, 2, 3, 4, and 8 changed + to 101, 102, 103, 104, and 108. + +0 "Error" as the complete answer without an explanation. + +0 Any list structure in the tree data. + +0 Anything else, including the "mutation" solution mentioned earlier with + 10 nodes like the original but with 1, 3, and 4 changed to 101, 103, 104. + + + +6. Scheme to OOP + +We are given + +(define foo + (let ((a 3)) + (LAMBDA (B) ;; This is the class FOO + (let ((c 4)) + (LAMBDA (MESSAGE) ;; This is the instance's dispatch procedure + (cond ((eq? message 'hi) + (+ a b)) + (else + (+ c message)))))))) + +The scope of the LET variable A encloses the procedure representing the class, +so it's a class variable. B is an argument to the class, so it's an +instantiation variable. And C is inside the scope of the class, but outside +the scope of the instance, so it's an instance variable -- each instance has +its own C. Therefore: + +(define-class (foo b) + (class-vars (a 3)) + (instance-vars (c 4)) + (method (hi) + (+ a b)) + (default-method + (+ c message))) + +The dispatch procedure looks explicitly for the message HI and provides +a method for it; the ELSE clause in the dispatch procedure handles any +other message, so it's a default method. + +Most people got the translation of the LET expressions for A and C right, +although a few people reversed them and a few people thought A and C were +the same kind of variable. B was trickier; some people didn't realize +that that LAMBDA represents the class, and instead thought that B was a +formal parameter of a method. + +Similarly, some people thought the inner LAMBDA expression represents a +method rather than a dispatch procedure, so they wrote methods with +MESSAGE as a parameter. + +As in any object class definition, it's possible to have only a default +method that checks for particular messages explicitly: + + (default-method + (if (eq? message 'hi) + (+ a b) + (+ c message))) + +and we accepted that, although it's contrary to the spirit of OOP. But +most people who were confused about the meaning of the inner LAMBDA came +up with incorrect solutions, such as + + (method (hi message b) ...) + (default-method (message) ...) + (method (hi) (if ...)) + +Scoring: The correct solution has five components: the use of B as an +instantiation variable, and the four clauses within the define-class (A, C, +HI, and DEFAULT-METHOD). We subtracted one point for each missing or +incorrect component. Incorrect solutions that tried to combine the HI +method with the default method lost both points, except for the + (method (hi) (if ...)) +version (no parameter to HI!), which lost only one point for the methods. + + +7. Environment diagrams + +The diagrams have many features in common: They all have a global frame +and an additional frame E1; they all have a symbol F bound to a procedure. +But there are two things that differ among diagrams: + + * The symbol F is in frame G (diagrams A and B) or in frame + E1 (diagrams C and D). + + * The procedure's right bubble points to frame G (diagrams + A and C) or to frame E1 (diagrams B and D). + +So, to figure out this question, for each of the four Scheme programs we +have to ask "where is the procedure created?" and "where is F bound?" + +(let ((f (lambda (x) x))) + 'okay) + + Here the LAMBDA expression is evaluated in the global environment, + because LET value expressions are evaluated *before* the implicit + procedure created by the LET is invoked. But the binding for F is + made locally, in the frame E1 that's created by the LET. So this + is diagram C: procedure points to G, F bound in E1. + +(define f + (let () + (lambda (x) x))) + + This time the LAMBDA expression is evaluated in the body of the LET, + so its current environment is E1, and so that's what the right bubble + remembers. But the DEFINE is in the global environment, so that's + where F is bound. This is diagram B: procedure points to E1, F + bound in G. + +(let () + (define f (lambda (x) x))) + + This time both the LAMBDA and the DEFINE are in the body of the LET, + so both of them have E1 as the current environment. This is diagram + D: procedure points to E1, F bound in E1. + +(define (f) f) +(f) + + Here we have a straightforward global definition of a procedure F, + so both the (implicit) LAMBDA and the DEFINE happen in G. So this + is diagram A: procedure points to G, F bound in G. (Frame E1 is + created by the second, separate expression, which invokes F.) + +Most students got this correct. The most common wrong answer was DBCA. +Choosing D for the first expression comes from the frequent misunderstanding +in which students think that the expressions that provide the values for the +LET variables are evaluated inside the scope of the LET. I'm not sure how +anyone would choose C for the third expression, but probably it's because you +assumed (correctly) that each diagram was used once. + +Scoring: one point each. + + +8. CADR for message-passing pairs + +A pair made by MAKE-PAIR can handle CAR and CDR messages directly because +its local state variables X and Y contain the desired values. But in order +to handle the CADR message, it has to find its own CDR (which is Y) and +send a CAR message to that other pair: + +(define (make-pair x y) + (lambda (msg) + (cond ((eq? msg 'car) x) + ((eq? msg 'cdr) y) + ((EQ? MSG 'CADR) (Y 'CAR)) ;; <<=== This line added! + (else (error "I have no idea what you're talking about.")) ))) + +One common mistake was (ASK Y 'CAR); this has the idea, but we're using +plain Scheme message passing, not the OOP language. + +Many students used roundabout means to find the pair's CDR, such as + + ((eq? msg 'cadr) (((make-pair x y) 'cdr) 'car)) + +presumably because you mistrusted a simple Y as something you can invoke. +This works, but it really violates the spirit of the problem -- it creates a +new pair every time you look at the pair -- and didn't get full credit. + +Another common error was (CAR Y). Unless you explicitly redefine CAR to +use the message-passing pairs, this will invoke the ordinary CAR that +expects a built-in Scheme pair as its argument, not a procedure. We +named the pair constructor MAKE-PAIR rather than CONS to make it clear +that we didn't mean to eliminate the regular pairs, and our example says +(ABC 'CAR) rather than (CAR ABC). + +Of course the worst mistake was to build the specific example ABC into +the solution! + +Scoring: + +3 Correct. + +2 (ASK Y 'CAR) + +2 (X 'CDR) ; this would give the CDAR, not the CADR. + +2 Working solutions that call MAKE-PAIR. + +1 (X 'CAR) or (Y 'CDR) ; CAAR and CDDR. + +0 Anything else, including (CAR Y). + + + +9. List mutation. + +Here is the box-and-pointer diagram *before* doing any mutation: + +---> XX------------> XX------------> X/ + | | | + V V V + + XX---> X/ XX---> X/ E + | | | | + V V V V + + A B C D + +The expression (SET-CAR! (CADR LST) (CDDR LST)) modifies the pair that is +the CADR of the original list -- the CAR of the CDR. (CDR LST) is the +second pair of the spine, in the top row. CAR of that pair is the first +pair in the spine of the sublist (C D). So we are going to change the CAR +of that pair, replacing C with something. With what? With the value of +(CDDR LST), the second argument to SET-CAR!. (CDDR LST) is the third +pair of the spine of the entire list, the one whose CAR is E. So after +this first mutation we have + +---> XX------------> XX---------->-> X/ + | | / | + V V * V + * + XX---> X/ XX---> X/ * E + | | * | * + V V * V * + * * + A B * D * + * * + ************ + +The second mutation, (SET-CAR! (CAR LST) (CADDR LST)), modifies (CAR LST), +which is the first element of the big list -- the first pair of the spine +of the sublist (A B). We change the CAR of this pair, so that instead of +pointing to A, it points to the CADDR of the big list, which is the third +element, the symbol E: + +---> XX------------> XX---------->-> X/ + | | / | + V V * V + * + XX---> X/ XX---> X/ * E + * | * | * + * V * V * ^ + * * * * + * B * D * * + * * * * + * ************ * + * * + ********************************* + +Notice that the first mutation points to a pair, not to E, but the second +one points to E. This is the difference between (CDDR LST) and (CADDR LST). + +It's okay if you draw another E underneath the relevant pair, instead of +drawing an arrow over to the original E. Since two equal symbols are always +EQ, it's not important to distinguish two equal symbols in the diagram. + +The third mutation is (SET-CDR! (CAR LST) (CDAR LST)). This says, "change +the CDR of (CAR LST) to the CDR of (CAR LST)"! In other words, it doesn't +really change anything: + +---> XX------------> XX---------->-> X/ + | | / | + V V * V + * + XX***> X/ XX---> X/ * E + * | * | * + * V * V * ^ + * * * * + * B * D * * + * * * * + * ************ * + * * + ********************************* + +Finally we have (SET-CAR! (CDDR LST) 'X). This modifies (CDDR LST), which +is the last pair of the spine. Its CAR used to point to E, but now points +to X instead: + +---> XX------------> XX---------->-> X/ + | | / * + V V * * + * V + XX***> X/ XX---> X/ * + * | * | * X + * V * V * + * * * + * B * D * E + * * * + * ************ ^ + * * + ********************************* + +So the printed representation of the final result is: + + ((E B) ((X) D) X) + +The most common wrong answer was ((X B) ((X) D) X). This comes from thinking +that the last mutation changes *everything* that points to E so that it points +to X instead. But that would be true only if the pair (CAR LST) pointed to +the *pair* (CDDR LST), whose CAR is changed from E to X, rather than pointing +directly to E. + +Another common wrong answer was ((E B) (X D) X), ignoring the fact that the +first mutation replaces the letter C with the *pair* (CDDR LST), which is a +list, not a symbol; its printed representation is (X). + +A common error in the diagram itself was to create new pairs, most often +making a *copy of* (CDDR LST) to be the CAR of (CADR LST). + +Another misunderstanding, which led to huge errors in the diagram, was to +think that (CAR LST) means the first *pair in the spine* of LST, rather +than the first *element* of LST. Similarly, students misinterpreted +(CADR LST) to mean the second pair of the spine, and so on. + +Scoring: We subtracted one point per wrong change in the diagram (out of +the four possible changes), and one point if the printed representation +didn't match your diagram. + + +10. Scheme vs Logo evaluators + +In Scheme, evaluating the expression (+ A 3) requires the evaluator to look up +two variables: + and A. Since we are giving MC-EVAL an environment that only +has a binding for A, this first expression gives the result + + ERROR: Unbound variable + + +In Logo, procedure names aren't part of the environment, but are found in a +separate, global table that's used automatically by LOGO-EVAL. So in order to +evaluate the Logo expression (SUM 2 :A), we have to look up A in the +environment, but we don't need SUM in the environment. Therefore the result +of this evaluation is + + 5 + + +One too-common error was to say (+ A 3) as the value returned in the first +case. Presumably students who said this were reacting to the fact that the +expression (+ A 3) is quoted when used as an argument to MC-EVAL. But this +just means that the argument is (+ A 3) rather than being the result of +evaluating (+ A 3) in the underlying STk evaluator! + +Scoring: Two points each. We accepted any ERROR message for the first part. + +For the second part, we accepted 6 instead of 5 (because it's not important +if you didn't notice that the second expression used 2 rather than 3) for +full credit. + +We gave half credit (one point) to either of two particular wrong answers +to the second part: + + You don't say what to do with 5 + +(which would be correct if we were calling DRIVER-LOOP instead of LOGO-EVAL), +and + + 5 =no-value= + +(which can't be correct, since it's two values instead of one, but presumably +is meant to show the values computed by EVAL-LINE, although that isn't right +either because EVAL-LINE returns a value as soon as it gets anything other +than =no-value= from evaluating an expression). + + +11. Streams + +The first two elements are explicitly given as A and B. The remaining +elements are the result of interleaving two streams, so we can draw a +picture like this: + + + A B ___ ___ ___ ___ + + ___ ___ ___ ___ + + +The second argument to INTERLEAVE is a stream containing only elements +that are the symbol B, so we can start to fill this in: + + + A B ___ ___ ___ ___ + + _B_ _B_ _B_ _B_ + + +To fill in the top row, we just copy the entire stream FOO. We already +know FOO's first two elements, so we can fill those in, and that tells us +FOO's third and fifth elements. (Its fourth element is the first B on the +bottom row.) + + + A B _A_ _B_ _A_ _B_ + + _B_ _B_ _B_ _B_ + + +Putting this back into a single row gives the solution: + + A B A B B B A B B B + + +Scoring: We subtracted one point per wrong letter. This means that the +common error in which only the first letter is A [A B B B B B B B B B B] +got one point. + +Exception: Some people apparently think that STREAM-FILTER keeps only +the elements that *don't* satisfy the predicate, so they put a stream of +As in the bottom row rather than a stream of Bs. This gives the incorrect +solution A B A A B A A A A A, to which we gave one point. + + +12. Logic programming + +As a reminder, here's ASSOC written in Scheme: + +(define (assoc key alist) + (cond ((null? alist) #f) + ((equal? key (caar alist)) (car alist)) + (else (assoc key (cdr alist))))) + +The first COND clause does not have any analog in the logic program! In +logic programming, if nothing satisfies the question we're asking, we just +don't match any rule. We don't want a rule that shows a value of #F. + +Here's the rule corresponding to the second COND clause: + +(assert! (rule (assoc ?key ((?key . ?value) . ?rest) (?key . ?value)))) + +No condition is necessary for this rule; the pattern says it all. But +it would be okay to show this rule in a form closer to that of the Scheme +program: + +(assert! (rule (assoc ?key (?car . ?cdr) ?car) + (and (same ?car (?caar . ?cdar)) + (same ?key ?caar)))) + +The second COND clause is a little tricky, because we only want to allow +the recursion if the key doesn't match the first entry. In Scheme, COND +automatically handles this, because COND can only return one value, so it +doesn't look at any clauses after the first successful one. But logic +programming allows multiple results, so we have to explicitly disable the +recursion in case of a match: + +(assert! (rule (assoc ?key ((?caar . ?cdar) . ?rest) ?result) + (and (assoc ?key ?rest ?result) + (not (same ?key ?caar))))) + +To make this work we also have to define the SAME relation: + +(assert! (rule (same ?x ?x))) + +but we didn't require this to be explicitly included in your solution. + + +Some people tried to use a single rule that matches any association list +that has the desired key anywhere in it, like this: + +(rule (assoc ?key (?left . (?key . ?value) . ?right) (?key . ?value))) ;WRONG! + +This isn't such a bad idea, except that there is no (x . y . z) notation for +a list that has element Y in the middle. But the desired result can be +obtained using the APPEND rules: + +(assert! (rule (assoc ?key ?alist (?key . ?value)) + (and (append ?left ((?key . ?value) . ?right) ?alist) + (not (assoc ?key ?left ?something))))) + +The NOT clause is required to eliminate duplicate matching keys. Alas, +most people who tried this didn't quite use APPEND correctly. The worst +problem was to try to use it as a function rather than a relation: + + (rule (assoc ?key (append ?left ((?key . ?value) . ?right)) + (?key . ?value))) ; WRONG!!! + +This is an attempt to use the "return value" from APPEND as part of the +pattern for the ASSOC rule, but APPEND doesn't return a value. It's a +relation that succeeds or fails, and the appended list is one of the +components of the relation, as in the correct version above. + + +The most common error was to include spurious base cases, such as + + (rule (assoc ?key () #f)) ; WRONG! + +A more subtle error was to try to eliminate duplicate keys in the +association list in the wrong rule: + +(assert! (rule (assoc ?key ((?key . ?value) . ?rest) (?key . ?value)) + (not (assoc ?key ?rest ?something)))) ; WRONG! + +This rule would find the last matching key, not the first matching key, +in the association list. + + +Scoring: + +5 Correct. + +4 Extracts just the key, or just the value, rather than the entire pair. + +4 Finds the last matching key rather than the first one. + +3 Finds all matching keys (no NOT clause). + +3 Spurious base case for empty list. + +2 No recursive rule at all. + +2 Other "has the idea" but non-working solutions with a rule that tries + to match the car of the association list. + +0 No rule matching the car of the association list (recursive rule only). + +0 Has the example built in (e.g., only works for lists of length four). + +0 Composition of functions (like the incorrect APPEND version above). + +0 Anything not mentioned above. + + +13. Concurrency + +All of the examples try to call the procedures F and G, which both modify +the variable X, and must therefore be protected against each other. +Therefore, we must use the same serializer for both of them. + +(parallel-execute (s f) (t g)) + + This uses two different serializers for the two thunks, so they + are not protected against each other. This can give rise to + INCORRECT RESULTS. + +(parallel-execute (s f) (s g)) + + This is the correct way to do it -- a single serializer protects + the variable X, and every process that depends on X is protected + using S. So it produces NEITHER incorrect results nor deadlock. + +(parallel-execute (s (t f)) (t g)) + + This has an unnecessary invocation of serializer S. Both processes + are protected by T, so no incorrect results are possible, and nothing + is added by calling S also. But since S is used for only one process, + there will be NEITHER incorrect results nor deadlock. + +(parallel-execute (s (t f)) (s g)) + + This is just like the previous case: S does the needed protection, + and T is unhelpful but not harmful either, since only one process + uses it. So NEITHER problem can arise. + +(parallel-execute (s (t f)) (t (s g))) + + There won't be incorrect results, since both processes use the same + serializer (either S or T can be considered as the useful one). The + second serializer is unnecessary. But this time, since two processes + use the same two serializers, in different orders, DEADLOCK is + possible. + +Scoring: One point each. + + +14. Tree to binary tree. + +The crucial point here is that two different abstract data types (Tree and +Binary Tree) are involved. A binary tree isn't just a Tree! It's different +because if a node has exactly one child, a Binary Tree can distinguish whether +this is the left child or the right child; the Tree type doesn't allow for +this distinction. So, for example, you couldn't use the Tree type to +represent a binary search tree. + +We are given a Tree as argument, and asked to return a Binary Tree. +Therefore, our program should use the *selectors* for the Tree type (namely +DATUM and CHILDREN), but should use the *constructor* for the Binary Tree +type (MAKE-BT). + +We didn't say explicitly in the problem what the arguments to MAKE-BT should +be, but we did say it's based on the Binary Tree type in the text (see page +157), except changing the name from MAKE-TREE to MAKE-BT. It takes three +arguments, the three components of a Binary Tree node: entry, left, and right. + +(define (tree->bt tree) + (if (> (length (children tree)) 2) + #f + (let ((kids (map tree->bt (children tree)))) + (cond ((member #f kids) #f) ; propagate failure upward + ((null? kids) (make-bt (datum tree) '() '())) + ((null? (cdr kids)) (make-bt (datum tree) (car kids) '())) + (else (make-bt (datum tree) (car kids) (cadr kids))))))) + +The most common error was to forget the first COND clause. It's not good +enough to return #F if *this* node has three or more children; we also have to +return #F if any *child* (or grandchild, etc.) of this node has too many +children. So we see if the value returned by any recursive call to TREE->BT +is false, and if so we return false too. + +Since MAKE-BT has separate arguments for the left and right branches, +we need three COND clauses for each of the possible number of children +in order to put the child(ren) in the right place(s). + +We accepted solutions in which MAKE-BT takes a list of length exactly two, +every time, to specify the two branches of the new node. But we didn't accept +solutions in which MAKE-BT takes a list of any number of children, because +that interface wouldn't allow the user to distinguish the case of a node with +only a left child from the case of a node with only a right child. (In this +problem we say that we aren't going to create any nodes with only a right +child, but you can't specify a constructor for Binary Trees that doesn't allow +for that possibility.) + +Another common error was data abstraction violations. These come in two +forms: (1) mixing the selectors and constructors for Trees with those for +Binary Trees, and (2) using list/pair selectors and constructors (CONS, CAR, +etc.) for either Trees or Binary Trees. We considered the first category less +severe than the second, although either kind of DAV really shows a failure to +understand the point of data abstraction! (This is true despite the fact that +a few students wrote essays to try to justify their violations.) + +Another severe error was to try to mutate the tree instead of constructing a +new data structure. This was rarely explicit (e.g., using SET-CAR!); the +usual thing was for students to call MAP, ignore its return value, and think +(apparently) that something has changed in the argument tree. We referred to +this in the grading as the "MAP!" error -- using MAP as if it were a mutator. + +Scoring: + +6 Correct. + +4 Correct except that #F from a child isn't propagated to the parent. + +2 Case analysis errors, e.g., two-child nodes handled correctly but + one-child nodes handled incorrectly. + +2 Tree vs. Binary Tree DAV. + +0 Tree vs. Pair DAV [e.g., (CAR TREE)]. + +0 No deep recursion (grandchildren not examined). + +0 Pseudo-mutation (using MAP as if it were MAP! mutator). + +0 Anything worse. + + + +15. SWAP! + +This was a relatively easy mutation problem, since there was no need to +examine inside any lists found as elements of the argument list. We only +care about elements of the top-level list. + +The first decision to be made is whether this is a job for SET-CAR! or +for SET-CDR!. The best choice is SET-CAR!, because we don't want to change +which pair comes first in the list's spine, in case some variable used in the +calling procedure is bound to this list. + +We want to mutate the pairs of the spine, not any pairs that might be elements +of the list. And we need a temporary variable to remember one of the elements +while we're doing the swapping. + +(define (swap! lst) + (cond ((null? lst) lst) + ((null? (cdr lst)) lst) + (else (let ((temp (car lst))) + (set-car! lst (cadr lst)) + (set-car! (cdr lst) temp) + (swap! (cddr lst)) + lst)))) + +Scoring: + +6 Correct. + +5 Swaps correctly but doesn't return a value. + +5 Correct except for base cases. + +4 Has the idea: + * Uses a temporary variable; and + * SET-CAR! of two pairs, with at least one in the spine; and + * Recursive; + but... + - recurs on (CDR LST) instead of (CDDR LST); or + - uses SET-CDR! and reorders correctly but loses the head pair; or + - has the wrong value in TEMP (a spine pair instead of an element). + +3 (set-car! (CAR lst) (cadr lst)) and (set-car! (CADR lst) temp). + +2 Has an idea: + - only one SET-CxR!; or + - no temporary variable; or + - mutates two wrong pairs; or + - thinks SET! will change a pair, but also uses SET-CxR!. + +0 Other, including: + - allocates pairs (CONS, LIST, APPEND, etc.); or + - no recursion; or + - no SET-CxR!; or + - SET! of a non-symbol [e.g., (SET! (CAR LST) (CADR LST))]. + + +16. Partial application in MCE + +The feature we want to add, which in the programming language literature is +generally called "partial application," is used when a procedure is called. +Procedure calling is the job of MC-APPLY, so that's where we have to make the +change. (It's possible to do it elsewhere, but less straightforward.) + +We are asked to construct a new procedure. How do we do that? The best +answer is to call MAKE-PROCEDURE. There's no need to construct and then +evaluate a LAMBDA expression! + +What should the procedure look like? One solution is to do exactly what's +shown in the question: a procedure whose body is an invocation of the +underlying procedure. But this is actually a little tricky, because when we +get to APPLY we no longer know what *expression* has that procedure as its +value! We only have the procedure itself. So the easiest thing will be if we +can create a procedure with the same body as the original procedure. For +example, if the original procedure is + + (lambda (base exp) + (cond ((= exp 0) 1) + ((even? exp) (fast-exp (* base base) (/ exp 2))) + (else (* base (fast-exp base (- exp 1)))))) + +then we'll create a procedure + + (lambda (EXP) ;; only this line is different + (cond ((= exp 0) 1) + ((even? exp) (fast-exp (* base base) (/ exp 2))) + (else (* base (fast-exp base (- exp 1)))))) + +but we'll create it in an environment with BASE bound to 2, as if the +user had typed + + (let ((base 2)) + (lambda (exp) + (cond ((= exp 0) 1) + ((even? exp) (fast-exp (* base base) (/ exp 2))) + (else (* base (fast-exp base (- exp 1))))))) + +But of course we can't build this particular example into the solution; +it has to work for any procedure, with any number of parameters, and with +any smaller number of arguments given in the invocation. + +(define (mc-apply procedure arguments) + (cond ((primitive-procedure? procedure) + (apply-primitive-procedure procedure arguments)) + ((compound-procedure? procedure) + (IF (< (LENGTH ARGUMENTS) (LENGTH (PROCEDURE-PARAMETERS PROCEDURE))) + (MAKE-PROCEDURE + (BUTFIRST-N (LENGTH ARGUMENTS) + (PROCEDURE-PARAMETERS PROCEDURE)) ; parameters + (PROCEDURE-BODY PROCEDURE) ; body + (EXTEND-ENVIRONMENT ; environment + (FIRST-N (LENGTH ARGUMENTS) + (PROCEDURE-PARAMETERS PROCEDURE)) + ARGUMENTS + (PROCEDURE-ENVIRONMENT PROCEDURE))) ; lexical scope! + (eval-sequence + (procedure-body procedure) + (extend-environment + (procedure-parameters procedure) + arguments + (procedure-environment procedure))))) + (else + (error + "Unknown procedure type -- APPLY" procedure)))) + +This solution uses helper procedures to extract the first N parameters, +and all but the first N parameters, from the original procedure's list of +parameters: + +(define (first-n n lst) + (if (= n 0) + '() + (cons (car lst) (first-n (- n 1) (cdr lst))))) + +(define (butfirst-n n lst) + ((repeated cdr n) lst)) + +This is the most elegant solution, because it deals only with values, +not with expressions -- there's no need to call MC-EVAL anywhere in it. +It's also possible to solve the problem by manipulating the text of the +procedure in various ways. For example, we could try to substitute the +argument values for the first N parameters in the body, so we'd get the +procedure + + (lambda (exp) + (cond ((= exp 0) 1) + ((even? exp) (fast-exp (* 2 2) (/ exp 2))) + (else (* 2 (fast-exp 2 (- exp 1)))))) + +for our example. This is trickier than it looks to get correct, though. +In this example the actual argument is a number, which is self-evaluating. +But suppose the actual argument value is a non-numeric word or a list. +It won't work to substitute the argument *value* into the body; we have +to find the argument *expression* (which means we'd have to do the job in +MC-EVAL rather than in MC-APPLY), or else we have to quote the value each +time we substitute it. + +The key point is to be clear on the difference between an expression and a +value -- for example, a LAMBDA expression versus a procedure. We want to +return a procedure, so either we call MAKE-PROCEDURE or we call + + (mc-eval (make-lambda ...) some-environment) + +Which environment should we extend? The one in the original procedure, +of course -- we don't want to break Scheme's lexical scope rule. Some +solutions passed the current environment from MC-EVAL to MC-APPLY, thereby +switching to dynamic scope. + +Many students came up with solutions modifying EXTEND-ENVIRONMENT instead of +modifying MC-APPLY. This is a reasonable first idea, since the problem is +about matching formal parameters with actual arguments, and that's the job of +EXTEND-ENVIRONMENT. But it's really tricky to get this right, because the +context in which EXTEND-ENVIRONMENT is called is that MC-APPLY is going to use +the resulting environment to evaluate the body of the procedure, and we don't +want to evaluate the body in the case of partial application. Some of you +actually managed to work around this problem by modifying EVAL-SEQUENCE as +well as EXTEND-ENVIRONMENT, something along these lines: + + (define (extend-environment vars vals base-env) + (if (= (length vars) (length vals)) + (cons (make-frame vars vals) base-env) + (if (< (length vars) (length vals)) + (error "Too many arguments supplied" vars vals) + (MAKE-PROCEDURE ...)))) + + (define (eval-sequence exps ENV-OR-PROC) + (cond ((COMPOUND-PROCEDURE? ENV-OR-PROC) ENV-OR-PROC) + ((last-exp? exps) (mc-eval (first-exp exps) env)) + (else (mc-eval (first-exp exps) env) + (eval-sequence (rest-exps exps) env)))) + +but this is an ugly solution. For one thing, EVAL-SEQUENCE might be used +someplace other than in MC-APPLY, so we shouldn't change its behavior without +thinking about those other callers. But even if the call to EVAL-SEQUENCE in +MC-APPLY is the only one in the program, it's ugly to have a procedure named +EVAL-SEQUENCE that sometimes doesn't actually evaluate a sequence! We +accepted working solutions on this model, but you shouldn't get in the habit +of designing this way. + + +Scoring: There are too many variants to list them all. We decided to group +them according to one central issue: do they actually return a procedure? + +6 Correct. + +5 Correct except for some trivial error. + +4 Has the idea: Checks for length mismatch between parameters and arguments, + and returns a procedure if there are fewer parameters, but something is + wrong with the new procedure's parameters, body, or environment. + +2 Has an idea: Checks for length mismatch, but then returns a lambda + expression, an environment, or something else that isn't an MCE procedure + (including an STk procedure formed by an underlying-Scheme LAMBDA + expression!). + +0 Anything else, including modifying only EVAL-SEQUENCE. diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-1.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-1.soln.txt new file mode 100644 index 0000000..80fa31f --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-1.soln.txt @@ -0,0 +1,423 @@ +CS 61A Solutions to sample midterm 1 #1 + +1. What will Scheme print? + +> (every - (keep number? '(the 1 after 909))) +(-1 -909) + + The KEEP part of the expression has the value (1 909), selecting the + numbers from the given sentence. (By the way, not everyone recognized + this as the name of a Beatles song, from the album _Let It Be_, the + last one they released, but the next-to-last one they recorded.) + + (every - '(1 909)) computes (- 1) and (- 909), putting the results in + a sentence. Some people thought this was an error because - requires + two arguments, but it doesn't. With one argument it means negation, + rather than subtraction. (Look it up in the Scheme reference manual + at the back of your course reader!) + + A few people said -908, because they thought EVERY would call the + function once, giving both numbers as arguments. That would be + (APPLY - '(1 909)), not EVERY. + + +> ((lambda (a b) ((if (< b a) + *) b a)) 4 6) +24 + + Substitute 4 for A and 6 for B in the body of the lambda: + ((if (< 6 4) + *) 6 4) + (< 6 4) is false, so the IF expression returns the multiplication + procedure, which is the value of the expression *. This procedure + is then called with 6 and 4 as its arguments. + + +> (word (first '(cat)) (butlast 'dog)) +CATDO + + The wrong answer we expected was CDO, but FIRST of a sentence is its + entire first word, even if there's only one word in it. Another + fairly common wrong answer was ERROR, presumably from people who + rightly thought that WORD won't accept a sentence as argument, but who + didn't see that FIRST of a sentence is a word, which makes it an okay + argument to WORD. + + A few people said CATOG because they didn't notice that it was + BUTLAST rather than BUTFIRST. We didn't take off for this. + +> (cons (list 1 2) (cons 3 4)) + +((1 2) 3 . 4) + + + --------- --------- + | | | | | | +--->| | | ------->| | | | | + | | | | | | | | | + --|------ --|---|-- + | | | + | V V + | + | 3 4 + | + V + --------- --------- + | | | | | /| + | | | ------->| | | / | + | | | | | | |/ | + --|------ --|------ + | | + V V + + 1 2 + + There were two important points to this problem: knowing the + difference between CONS and LIST, and knowing how Scheme prints + improper lists. (The two upper pairs in the diagram form the + spine of an improper list, which is a cdr-linked set of pairs in + which the cdr of the last pair isn't the empty list.) + + +> (let ((p (list 4 5))) + (cons (cdr p) (cddr p)) ) + +((5)) + + p is bound to (4 5) + (cdr p) evaluates to (5), and (cddr p) evaluates to () + (cons '(5) '()) evaluates to ((5)) + +Box and pointer diagram: + +---+---+ +--->| o | / | + +-+-+---+ + | + v + +---+---+ + | o | / | + +-+-+---+ + | + v + 5 + +> (cadadr '((a (b) c) (d (e) f) (g (h) i))) +(e) + +--->X/ + | + V + e + + We didn't take off for including other pairs from the large argument + in your picture, as long as there was a clear start arrow showing + where the return value starts. + + The quickest way to solve this problem is to remember that CADR means + the second element, and to view CADADR as (CADR (CADR ...)) -- the + second element of the second element of the argument. Alternatively, + we can spell it out step by step: + + (cdr '((a (b) c) (d (e) f) (g (h) i))) ==> ((d (e) f) (g (h) i)) + (car '((d (e) f) (g (h) i))) ==> (d (e) f) + (cdr '(d (e) f)) ==> ((e) f) + (car '((e) f)) ==> (e) + + The crucial point is to see that it's CAR of CDR of CAR of CDR of the + list, which means the first step is CDR -- you have to work from + inside out, which in a case like this means from right to left. If + you start by taking the CAR of the big list, you end up with the empty + list. + + + +Scoring: one point each. + + +2. Order of growth + +(define (foo n) + (if (< n 2) + 1 + (+ (baz (- n 1)) + (baz (- n 2)) ))) + +(define (baz n) + (+ n (- n 1))) + +FOO is Theta(1). + + Since FOO calls BAZ twice, we have to know the running time of BAZ + before we can figure out the running time of FOO. + + BAZ does not contain any recursive calls, either to baz itself or to + foo. Rather, it performs two fixed-time operations, an addition and a + subtraction, and so its running time is Theta(1). + + Therefore, everything FOO does is fixed-time! It calls <, +, -, and + BAZ, all of which are Theta(1). And so FOO itself is also Theta(1). + + The most frequent wrong answer was Theta(2^n). People who thought + that put too much weight on the *form* of procedure FOO. They saw two + procedure calls, and thought that the process was therefore comparable + to the Fibonacci computation or the Pascal's Triangle computation. + But in those cases, the two calls are *recursive* calls, not calls to + a fixed-time helper. + +(define (garply n) + (if (= n 0) + 0 + (+ (factorial n) (garply (- n 1))) )) + +(define (factorial n) + (if (= n 0) + 1 + (* n (factorial (- n 1))) )) + +GARPLY is Theta(n^2). + + GARPLY calls itself recursively N times, so it's tempting to think + that it's Theta(n), the most common wrong answer. But each of those N + invocations of GARPLY includes an invocation of FACTORIAL, which is + itself Theta(n). So N calls to a Theta(N) procedure makes a total of + N*N fixed-time operations. + +Scoring: one point each. + + +3. Normal and applicative order. + +The expression (* (counter) (counter)) has the value 2 under both +applicative and normal order. + +Under applicative order, all subexpressions are evaluated before * is called. +There are two subexpressions of the form (counter), each of which is +evaluated separately. The first evaluation returns 1; the second returns 2. +(It doesn't matter whether they are evaluated left to right or right to +left, since 1 times 2 = 2 times 1.) + +Under normal order, you might think that things would get more complicated, +but since * is a primitive (as the problem statement says), its arguments +are evaluated before it is invoked even under normal order. It's only +arguments to user-defined procedures that are handled differently. + +But even if we did something like this: + + (define (times a b) + (* a b)) + + (times (counter) (counter)) + +it wouldn't change the result. Normal order *would* affect the call to +TIMES, so that instead of substituting 1 and 2 for A and B, we'd +substitute the expression (COUNTER) for both A and B in the body of +TIMES. The result of that substitution would be + + (* (counter) (counter)) + +which is the same thing we started with. + +The most common error was to say that the answer would be 1 under applicative +order. People who said that were confusing this problem with a different one, +more like what I did in lecture: + + (define (square x) + (* x x)) + + (square (counter)) + +For *that* problem, the answer would be 1 under applicative order and 2 under +normal order. But this is the opposite of the situation you were given. +Normal order can turn one subexpression into multiple copies (which are then +separately evaluated), but it can't turn two expressions, even if identical, +into a single expression to be evaluated once. + +Interestingly, almost as many people said that the answer would be 1 under +*normal* order. My guess is that they were thinking of the square problem, +but instead of actually working through that problem, they just remembered +that normal order is the one that gives the weird answer. :-) + +Scoring: 1 point, all or nothing. + + +4. Recursive or iterative process? + +(define (butfirst-n num stuff) + (if (= num 0) + stuff + (butfirst-n (- num 1) (bf stuff)))) + +ITERATIVE PROCESS. The recursive call is the last thing the procedure has +to do. (It's inside an IF, but it isn't evaluated until after IF has decided +which branch to take.) + + +(define (member? thing stuff) + (cond ((empty? stuff) #f) + ((equal? thing (first stuff)) #t) + (else (member? thing (bf stuff))))) + +ITERATIVE PROCESS. Again, the recursive call is the last thing the +procedure has to do. + + +(define (addup nums) + (if (empty? nums) + 0 + (+ (first nums) + (addup (bf nums))))) + +RECURSIVE PROCESS. The recursive call is the last *line* of the procedure +definition, but it's inside a call to the + procedure, so the after the +recursion finishes we still have to call +. + +Scoring: one point each. + + +5. Recursive procedures. + +This is the only one that I didn't expect to be immediately obvious +to all of you. There are lots of ways to do it. Here is the one +suggested by the hint: + +(define (syllables wd) + (define (chop wd) + (cond ((empty? wd) "") + ((vowel? (first wd)) + (chop (bf wd))) + (else wd)) ) + (cond ((empty? wd) 0) + ((vowel? (first wd)) (+ (syllables (chop wd)) 1)) + (else (syllables (bf wd))) )) + +Another way is to count a vowel only if the next letter isn't one: + +(define (syllables wd) + (cond ((empty? wd) 0) + ((vowel? (first wd)) + (cond ((empty? (bf wd)) 1) + ((vowel? (first (bf wd))) (syllables (bf wd))) + (else (+ (syllables (bf wd)) 1)) )) + (else (syllables (bf wd))) )) + +Yet another way is to use a state variable to remember whether +or not the previous letter was a vowel: + +(define (syllables wd) + (define (s1 wd was-cons) + (cond ((empty? wd) 0) + ((vowel? (first wd)) (+ was-cons (s1 (bf wd) 0))) + (else (s1 (bf wd) 1)) )) + (s1 wd 1) ) + +There were too many kinds of errors to list. The trick here is +that the program structure can't be exactly like the examples +seen earlier, but you have to cope with that while not forgetting +everything you know about functional programming. For example, +many people wanted to keep a count of the number of syllables so +far in a state variable, so they said things like + (if (vowel? (first wd)) + (+ count 1) + (... something else ...)) +as if + CHANGED THE VALUE of the variable count. Thinking in BASIC! + + +6. Higher order procedures. + +(define (in-order? pred sent) + (cond ((empty? sent) #t) + ((empty? (bf sent)) #t) + ((pred (first sent) (first bf sent)) + (in-order? pred (bf sent)) ) + (else #f) )) + +(define (order-checker pred) + (lambda (sent) (in-order? pred sent)) ) + +One common error was to use (in-order? pred (bf (bf sent))) as the +recursive step, on the theory that the first two elements have already +been looked at. The trouble is that you have to compare overlapping +pairs of elements. For example, (in-order? < '(2 8 5 9)) should be +false, even though 2<8 and 5<9, because 8>5. + +Scoring: For part (a), three if it's right, two if it's correctly +typed (that is, your procedure takes a two-argument predicate and +a sentence as arguments, and returns true or false), one if it has +some idea, zero if not. For part (b), two if it's right, one if +it's correctly typed (takes a predicate function of two arguments +and returns a predicate function of one argument), zero if not. + + +7. Time ADT + +(define (time-print-form time) + (word (hour time) ': (two-digit (minute time)) (category time))) + +(define (two-digit num) + (if (< num 10) + (word 0 num) + num)) + + +(define (24-hour time) + (+ (* (hour time) 100) + (minute time) + (if (equal? (category time) 'pm) 1200 0))) + + +(define (make-time hr min cat) + (+ (* hr 100) + min + (if (equal? cat 'pm) 1200 0))) + +(define (hour time) + (if (>= time 1200) + (- (div time 100) 12) + (div time 100))) + +(define (minute time) + (remainder time 100)) + +(define (category time) + (if (>= time 1200) 'pm 'am)) + + +The most common serious errors were writing a non-function in part (a) and +rewriting make-time with the wrong number of arguments in part (c). These +errors were the ones that gave rise to the most complaints about harsh +grading, but I really think they're about crucial issues in the course. + +Part (a) says, "Write a FUNCTION time-print-form that takes a time as its +argument and RETURNS a word of the form 3:07pm." In week 7 of the course +you should know what it means for a function to return a value! Some people +said they were confused by the fact that the word "print" is part of the +function's name, but a "print form" is the form in which we want things to +be printed; computing the print form of a time doesn't mean that we should +actually print it! Maybe the print form will be used as part of a larger +sentence that we'll want to print later. + +Part (c) says, "Now we decide to change the *internal* representation of +times to be a number in 24-hour form. BUT WE WANT THE CONSTRUCTOR AND +SELECTORS TO HAVE THE SAME INTERFACE SO THAT PROGRAMS USING THE ABSTRACT +DATA TYPE DON'T HAVE TO CHANGE." That means that the arguments to make-time +must be the same things they were all along: an hour (in 12-hour time), a +minute, and a category (am/pm). + + +Many people returned 3:7pm instead of 3:07pm in part (a), because they +thought that it would be sufficient to say something like + (time-print-form (make-time 3 07 'pm)) +The trouble is that Scheme interprets 07 as the number 7; Scheme doesn't +remember exactly how you typed the number. This was a minor error. + +Many people, in part (c), changed the internal representation to something +other than a number, e.g., a list of two numbers. I've spoken with four +students who didn't understand why this was wrong, and I asked them to +read the first sentence of part (c), and they said "... representation of +times to be in 24-hour form." And I said, "No, read it again." On the +third or fourth try they'd finally read the words "a number." Sigh. + +Typical errors and scores: + +4 3:7pm +3 changes internal form to (15 7) instead of 1507 +2 printing in (a) or wrong args in (c), as above +1 glimmers of using the abstraction diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-2.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-2.pdf new file mode 100644 index 0000000..e7f1e90 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-2.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-3.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-3.pdf new file mode 100644 index 0000000..09e97c3 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm1/mt1-3.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.pdf new file mode 100644 index 0000000..0b90000 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.soln.txt new file mode 100644 index 0000000..e80be44 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.soln.txt @@ -0,0 +1,411 @@ +CS 61A Solutions to sample midterm 2 #1 + +1. What will Scheme print? + +Note: Please draw actual boxes, as in the book and the lectures, not XX and X/ +as in these ASCII-art solutions. + +Also, please put in the start arrows! Sometimes it's hard to know where your +diagrams are supposed to begin, especially if you use leftward and upward +pointing arrows. + +> (map caddr '((2 3 5) (7 11 13) (17 19))) +ERROR + + (caddr '(2 3 5)) is 5; (caddr '(7 11 13)) is 13. But (17 19) + doesn't have a caddr, which would be the third element of a + two-element list. The error is attempting to take the car of + the empty list. + + The most common wrong answer was (5 13), thinking that the error + would just slide under the rug. + +> (list (cons 2 (cons 3 5))) +((2 3 . 5)) + + +--->X/ + | + XX--->XX---> 5 + | | + V V + 2 3 + + There were two points to note in this problem: (cons 3 5) creates + an improper list, and LIST is called with one argument, making a + one-element list (whose spine is the topmost pair in the diagram). + + One error was to think that every call to CONS results in something + that prints with a dot, like this: ((2 . (3 . 5))) But in fact + Scheme never prints a dot if the cdr is a pair; if the ultimate + pair of a chain of cdr-linked pairs doesn't have the empty list as + its cdr, you get the improper list notation (2 3 . 5) + + The extra parentheses in the printed form show that the result is + a one-element list whose element is a list structure (in this case, + an improper list rather than an actual list). + + +> (append (list '(2) '(3)) (cons '(4) '(5))) +((2) (3) (4) 5) + + +--->XX--->XX--->XX--->X/ + | | | | + V V V V + X/ X/ X/ 5 + | | | + V V V + 2 3 4 + + The most problematic part of this for most students was the CONS. + Some people, remembering that the arguments to APPEND must be + lists, said that this produced an error -- but of course CONS can + produce a list, if its second argument is a list, as it is here. + [Fine print: In fact the *last* argument to APPEND is *not* required + to be a list, although the others are. See the Scheme reference + manual.] In this case, the CONS call produces the list ((4) 5). + The asymmetry in the handling of (4) and (5) comes from the meaning + of CONS in creating a list: the first argument, the car of the new + pair, is an *element* of the resulting list, whereas the second + argument, the cdr of the new pair, is a *sublist* of the resulting + list. If this confuses you, think about what you'd expect + (cons 4 '(5)) + to do. + + The most common error, still about the CONS call, was to see that + it has to do something different from the LIST call, but still + try to make it treat its arguments symmetrically, resulting in + the wrong answer ((2) (3) 4 5). + + +> (list (cons '(0) '(1)) (append '(2) '(3))) +(((0) 1) (2 3)) + +--->XX------------->X/ + | | + V V + XX--->X/ XX--->X/ + | | | | + V V V V + X/ 1 2 3 + | + V + 0 + + LIST returns a list with as many elements as it has arguments -- in + this case, two elements. The top two pairs in the diagram are the + ones generated by LIST. + + CONS generates exactly one new pair. In this problem, the first pair + on the second line of the diagram is the one generated by CONS. Its + car is the pair on the third line, which is the list (0); its cdr is + the second pair on the second line, which is the list (1). The + important thing to see here is that the lists (0) and (1) do not play + similar roles in the result, because of the way lists are defined. + The car of a pair is a list *element*; the cdr of the same pair is a + *sublist*. So the value returned by the CONS invocation is a list of + two elements, namely (0) and 1 -- not (0) and (1); not 0 and 1. + + APPEND strings together the elements of its arguments, so in this + case, the result of the APPEND invocation is the list (2 3). + +There were two common wrong answers to this part. One mistake was to put +the last element of a sublist in the cdr of a pair, like this: + +--->XX------------->X/ ; WRONG! + | | + V V + XX--->1 XX--->3 + | | + V V + X/ 2 + | + V + 0 + +The numbers 1 and 3 are attached to the cdrs of their parent pairs, +rather than to the cars. + +The other common mistake was to leave out the pair just above the zero, +like this: + +--->XX------------->X/ ; WRONG! + | | + V V + XX--->X/ XX--->X/ + | | | | + V V V V + 0 1 2 3 + +A less common, but more serious, error was to leave out part of the +work by having parentheses in the diagram: + +--->XX------------->X/ ; WRONG! + | | + V V + XX--->(1) XX--->(3) + | | + V V + (0) 2 + +There are never any parentheses in a box and pointer diagram. The +parentheses in the *printed representation* of a list structure are +just a notation to represent *pairs* in the actual structure. + + +Scoring: One point for each printed result; one point for each diagram, +except for the first part, which got two points or none. + + +2. Binary search trees + +Although the ADT doesn't include empty trees, the program is easier to +write if you allow for the possibility of getting an empty list as +argument instead of a tree, because that's what happens when you try to +recur for the children of a leaf node. On that assumption, here's one +way to write it: + +(define (all-smaller? tree num) + (or (null? tree) + (and (< (entry tree) num) + (all-smaller? (left-branch tree) num) + (all-smaller? (right-branch tree) num)))) + +(define (bst? tree) + (or (null? tree) + (and (all-smaller? (left-branch tree) (entry tree)) + (all-larger? (right-branch tree) (entry tree)) + (bst? (left-branch tree)) + (bst? (right-branch tree))))) + +Most people wrote equivalent programs using COND, which is fine, but I +find this style cleaner when writing predicates. + +A BINARY TREE is just a tree in which each node has at most two +children. A BINARY SEARCH TREE is a binary tree with the ordering +constraints as described in the text. The text doesn't make that +entirely clear, because their only use of binary trees is to represent +the SET ADT, for which a BST is needed. Therefore, we didn't take off +points if in part (a) you assumed the ordering relationship and therefore +only checked the right branch of the tree, as long as you did the tree +recursion properly in (b). + +Scoring: This and the remaining problems are graded on the scale + 5 correct + 3-4 has the idea + 1-2 has an idea + 0 other + +Having the idea, in this problem, means doing a tree recursion. The most +common form of not having the idea was to think, in part (b), that the +ordering must be checked only with respect to the root node, so you left +out the recursive calls to BST?. + +We took off one point if you violated the binary tree ADT, using CAR and +CDR instead of ENTRY, LEFT-BRANCH, and RIGHT-BRANCH. (If you thought +that those three things are names of trees, rather than of procedures, +you didn't have the idea.) + +A too-common error was to say things like + (< (left-branch tree) (entry tree)) +as if the left branch were a number! It's not; it's a tree. + + +3. Tree fanout. + +The best answer is + +(define (max-fanout tree) + (accumulate max + (length (children tree)) + (map max-fanout (children tree)))) + +This takes advantage of the fact that ACCUMULATE requires a starting value +for the accumulation, usually 0 or 1 in the book's examples, but we can use +the fanout of this node as the starting value. + +Here's the non-higher-order, mutual-recursion version: + +(define (max-fanout tree) + (max (length (children tree)) + (max-fanout-forest (children tree)))) + +(define (max-fanout-forest forest) + (if (null? forest) + 0 + (max (max-fanout (car forest)) + (max-fanout-forest (cdr forest))))) + +Some people made this more complicated by using a one-element forest as +the base case in max-fanout-forest, thereby requiring that max-fanout +check for the special case of a leaf node. If this were a general +problem about accumulating the MAX of arbitrary numbers, we couldn't use +0 as the base case, because all the numbers might be negative, so if +anything the base case would have to be negative infinity. But here +the numbers are node fanouts, and there's no such thing as a negative +number of children! + +Note that max-fanout does not need a base case. The recursion happens +either in MAP, for the first solution, or in MAX-FANOUT-FOREST, for +the second solution. + +Having the idea, in this problem, mostly meant understanding the Tree ADT. +The totally wrong solutions were ones that applied CAR and CDR to a Tree -- +or, equivalently, the ones that said DATUM and CHILDREN but meant CAR and +CDR. Note that there is no reference to DATUM in a correct solution to +this problem! The fanout has nothing to do with the values in the nodes, +only with the Tree's shape. + +Not only is CAR/CDR recursion a data abstraction violation, it's also a +fundamental misunderstanding of this particular problem. It's often the +case that similar problems could be posed for abstract Trees and for +list structures viewed as trees. But if you use CAR/CDR recursion, you +are thinking of each pair as a node in a binary tree, essentially, so +the fanout is always 2! The whole issue of fanout doesn't arise unless +you have real Trees to think about. + +CAR/CDR programs, or their equivalent -- such as programs with expressions +of the form (not (pair? tree)) -- got at most 2 points, but more often 0 or 1. +So did programs that confused trees with forests. + +Some not-so-bad programs tried to apply MAX to a list of lists of numbers, +rather than to a list of numbers. Our general rule was that if we could +fix your program by replacing a call to MAP with a call to FLATMAP, it +got 3 points. + +A common problem, not so bad, was to get confused about the domain of MAX. +This procedure takes numbers as arguments, not lists; you can't say + (max '(1 2 3 4)) +but you *can* say + (apply max '(1 2 3 4)) +or in this case, because all the numbers are positive, + (accumulate max 0 '(1 2 3 4)) +The advantage of ACCUMULATE over APPLY is that in some cases, people who +used APPLY ended up applying MAX to an empty list -- in other words, trying +to call MAX with no arguments. That's not allowed, but ACCUMULATE always +calls MAX with exactly two arguments, if at all, so it doesn't have the +same potential bug. All problems in this category lost only one point. + +The comments in the solution to question 2 about making unnecessary data +structures apply here, too. Several people made trees in which the datum +of each node was replaced by its fanout. Others made linear sequences of +tree nodes. All of these things only complicate the program; whatever you +end up doing to create the structure and then process it could instead +solve the problem directly in one step. + +Scoring: 3 or more points for a solution that uses the Tree ADT correctly +and actually computes fanouts and maximums. 2 or fewer points for a solution +with car/cdr recursion, tree/forest confusion, nothing about fanouts, or +nothing about maximum. + + +4. Data-directed programming. + +(define (plus x y) + (let ((tx (type x)) + (ty (type y))) + (if (eq? tx ty) + (attach-tag tx (+ (contents x) (contents y))) + (let ((gxy (get tx ty)) + (gyx (get ty tx))) + (cond ((number? gxy) + (attach-tag ty (+ (* gxy (contents x)) (contents y)))) + ((number? gyx) + (attach-tag tx (+ (contents x) (* gyx (contents y))))) + (else (error "You can't add apples and oranges."))))))) + + +The use of LET in this solution isn't essential; various rearrangements +are possible and are equally good. + +Surprising numbers of people had trouble understanding what the problem +was asking for. They wrote programs in which 3 dynes PLUS 4 centimeters +equals 12 ergs! Sorry, 3 plus 4 is not 12 no matter how clever your +coding style is. As the problem clearly stated, you were asked to write +one procedure, the addition procedure, for a larger project that would +also include a multiplication procedure when completed. Moral: don't +be in such a hurry to write code. Make sure you understand the problem +you are being asked to solve first! + +Another common way to get in trouble was to try to apply the number you +found in the table (12, in the example) as a procedure. Just because +there is an example in the book in which a table contains procedures as +entries, that doesn't mean that every table has to contain procedures! +This particular table contains numbers, for units that can be added +together, and symbols, for units that can be multiplied. + +Scoring: 8 points for a perfect solution. + 4-7 points for a flawed solution not grossly confused. + 2-3 points for a grossly confused but not clueless solution. + 0-1 point for a solution showing no understanding at all. + +In general we subtracted two points for each flaw, down to the +minimum for the categories as indicated. Here are some 2-point errors +that bottomed at 4 points: + +-- not checking the number? predicate +-- not checking for the arguments being backwards in the table +-- incorrect conversion formula +-- violation of the attach-tag data abstraction +-- wrong args to GET + +Here are some errors eligible for the 2-3 point range: + +-- checking explicitly for 'ft or 'in +-- applying a non-procedure +-- Lisp syntax errors like non-symbol formal parameters + + +5. OOP + +The central point of this question is that in the OOP paradigm, objects are +used for everything, and the structure of the object classes reflects the +structure of the real-world situation being simulated. + +(a) parenthood + +The class VANILLA has the class SCOOP as its parent, because a vanilla scoop +is a particular kind of scoop. + +Is a scoop a special kind of cone? No. + +Is a cone a special kind of scoop? No. + +So the correct answer is "Neither." Most people got this; the most common +wrong answer was to say that SCOOP should have CONE as its parent, probably +because a scoop can be viewed as *part of* a cone. But the parent/child +relationship isn't "a part of"; it's "a kind of." + +(b) flavors method + +(method (flavors) + (map (LAMBDA (S) (ASK S 'FLAVOR)) scoops)) + +You *could* write the CONE class so that its instance variable SCOOPS would be +a list of flavors (i.e., names of flavors) instead of a list of scoop objects. +But that wouldn't be following the OOP paradigm. (Not to mention that using +the name SCOOPS for a list of flavors would be really confusing!) So if we +want to know the flavors in a cone, we have to ask each scoop for its flavor. + +A few people said something like (USUAL 'FLAVOR) instead of (ASK S 'FLAVOR), +presumably because FLAVOR is a method of the SCOOP class, rather than of the +VANILLA or CHOCOLATE class. But even if this could work, the whole idea of +inheritance is that you can send the child class (e.g., VANILLA) the same +messages you can send to the parent class (SCOOP). You don't have to know +whether VANILLA handles the FLAVOR message itself or delegates the message to +its parent. And in any case it wouldn't work; USUAL can only be used inside +a DEFINE-CLASS, because otherwise it doesn't know what object you're talking +about! + + +(c) adding a scoop + +Given a particular ice cream cone, we want to add a particular scoop of +vanilla ice cream to it -- not the VANILLA class, and not the word VANILLA. +So the right answer is the last one listed: + (ask my-cone 'add-scoop (instantiate vanilla)) +The argument to INSTANTIATE is a class, not the name of a class. + +Scoring: 2 points each. No partial credit except that in part (B) leaving +out the quotation mark before FLAVOR got one point. diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-2.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-2.soln.txt new file mode 100644 index 0000000..701905a --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-2.soln.txt @@ -0,0 +1,609 @@ +CS 61A Solutions to sample midterm 2 #2 + +1. What will Scheme print? + +Please put in the start arrows! Sometimes it's hard to know where your +diagrams are supposed to begin, especially if you use leftward and upward +pointing arrows. + +> (list (cons 2 3) 4) +((2 . 3) 4) + + +---+---+ +---+---+ + | | | | | /| +--------->| | | ------->| | | / | + | | | | | | |/ | + +-|-+---+ +-|-+---+ + | | + | V + | + | 4 + | + V + +---+---+ + | | | + | | | | | + | | | | | + +-|-+-|-+ + | | + V V + + 2 3 + +Most people got this. The ones who didn't most often left out the dot +in the printed version. + + +> (append (cons '(a) '(b)) '(c)) +((A) B C) + + +---+---+ +---+---+ +---+---+ + | | | | | | | | /| +---------> | | | ----->| | | ----->| | | / | + | | | | | | | | | | |/ | + +-|-+---+ +-|-+---+ +-|-+---+ + | | | + | V V + | + | B C + V + +---+---+ + | | /| + | | | / | + | | |/ | + +-|-+---+ + | + V + + A + +Many people were confused about this one, especially the CONS part. +Here is a box and pointer diagram of (cons '(a) '(b)). The starred +pair is the one created by the CONS: + + + *********** + *+---+---+* +---+---+ + *| | |* | | /| +--------->*| | | ----------->| | | / | + *| | | |* | | |/ | + *+-|-+---+* +-|-+---+ + ***|******* | + | V + | + | B + | + V + +---+---+ + | | /| + | | | / | + | | |/ | + +-|-+---+ + | + V + + A + +Even though this structure was created using CONS rather than LIST, +it's a list, because the cdr of the new pair is a list. This list +has two elements; the first is (A) and the second is B. So in +effect the call to APPEND is (append '((a) b) '(c)). + +We weren't very sympathetic to people who drew diagrams like this: + + +---+---+ + | | | +---------->| | | ------> etc + | | | | + +-|-+---+ + | + V + + (A) + +Things in parentheses in the printed representation must be shown +as pairs in the diagram! + + + +> (cdadar '((e (f) g) h)) +() + +Note that the result is (), not '()! + +There really is no need for a box-and-pointer diagram for an empty +list, which is an atom. We accepted + + +---+ + | /| +---------->| / | + |/ | + +---+ + +but *NOT* this: + + +---+---+ + | /| /| +---------->| / | / | + |/ |/ | + +---+---+ + +because that would be a pair, representing the list (()), not an empty list. + +Some people got this wrong because they figured the cdadar incorrectly. +Here's how to get there: + +(car '((e (f) g) h)) ===> (e (f) g) +(cdr '(e (f) g)) ===> ((f) g) +(car '((f) g)) ===> (f) +(cdr '(f)) ===> () + +CDADAR is an abbreviation for (cdr (car (cdr (car ...)))), so you have +to start at the inside and take the CAR of the argument first. Some +people read CDADAR left to right as "take the cdr, then the car, ..." +but that's wrong. + +Scoring: One point for each, with both printed form and b&p diagram +correct to get the point. One point total for people who got all three +printed results correct but left out the b&p diagrams. + + + +2. Fill in the blank. + +> (CADADR '(g (h i) j)) +I + + +The letter I is the second element of (H I), so it's + (cadr '(h i)) +But the sublist (h i) is the second element of the entire argument, +so it's + (cadr '(g (h i) j)) +So we want + (cadr (cadr '(g (h i) j))) +and that's abbreviated as CADADR. + +Scoring: one point, all or nothing! + + +3. Proj2 data abstraction + +(a) Type-tagged segment ADT. The solution we wanted was this: + +(define (make-segment start end) + (attach-tag 'segment (cons start end))) + +(define (start-segment seg) + (car (contents seg))) + +(define (end-segment seg) + (cdr (contents seg))) + +Alternatively, you could use LIST instead of CONS and CADR instead of CDR. + +Here is the crucial point to understand about data abstraction: WE WANT +THIS CHANGE NOT TO BREAK EXISTING PROCEDURES IN THE PROJECT! That means +that start-segment, for example, must return a vector, just as it did +before the change. + +Some people wrote + +(define (start-segment seg) ;; wrong!!! + (attach-tag 'segment (car seg))) + +One problem with this is that the start-segment of a segment isn't the +car of the argument anymore, once we have a type attached. But it's +much worse to attach the SEGMENT type to the result, because the result +isn't a segment! It's a vector. + +Other people gave make-segment only one argument. Probably this means +that you don't know what a segment is, because you let your partner do +all the work on the project. + + +Scoring: +2 As shown above. +1 Working code, but not respecting the tagged-data abstraction + (e.g., cons instead of attach-tag, cadr and cddr in the selectors). +0 Anything else. + + +(b) Find the midpoint of a segment or frame. + +(define (midpoint shape) + (cond ((eq? (type-tag shape) 'segment) + (scale-vect 0.5 + (add-vect (start-segment shape) + (end-segment shape)))) + ((eq? (type-tag shape) 'frame) + ((frame-coord-map shape) (make-vect 0.5 0.5))) + (else #f))) + +We accepted less elegant but correct algorithms for the midpoints of +the shapes. For a segment another approach is + + (make-vect (/ (+ (xcor-vect (start-segment shape)) + (xcor-vect (end-segment shape))) + 2) + (/ (+ (ycor-vect (start-segment shape)) + (ycor-vect (end-segment shape))) + 2)) + +For frames we saw two other correct approaches. One was essentially +to rewrite frame-coord-map: + + (add-vect (origin-frame shape) + (scale-vect 0.5 + (add-vect (edge1-frame shape) + (edge2-frame shape)))) + +Another was to find the midpoint of a diagonal of the parallelogram: + + (midpoint (make-segment (add-vect (origin-frame shape) + (edge1-frame shape)) + (add-vect (origin-frame shape) + (edge2-frame shape)))) + +Most people had correct algorithms for the midpoint of a segment. There +were two common incorrect algorithms for frames; one wrong approach was +to ignore the frame's origin, and the other was to assume that the frame's +edge1 contributes only to the x-coordinate of the midpoint and that its +edge2 contributes only to the y-coordinate. + +One reason for incorrect solutions to the midpoint of a frame was that +people confused the origin of the FRAME with the origin of the COORDINATE +SYSTEM -- that is, the point (0, 0). The vector returned by +(origin-frame shape) points from the coordinate system origin (0, 0) to +the frame's origin, which is one of its corners. That corner might or +might not be at (0,0)! For example, when you wrote procedures like +BELOW in the project that combine two pictures in adjacent frames, at +least one of those frames doesn't begin at (0, 0). + +Some people wrote a data-directed solution, including things like + + (put 'frame 'midpoint frame-midpoint) + +This was okay, but more work than the problem required. Other people +tried to use message passing, with less success. A correct use of +message passing means that the data -- the frames and segments -- must +be represented as procedures: + +(define (make-segment start end) + (lambda (message) + ...)) + +But this is incompatible with part (a)! Some people tried to use a +dispatch procedure for the *operator*: + +(define (midpoint shape) ;; wrong! + (lambda (message) + ...)) + +but that doesn't make any sense. You send messages to objects, not +to operators. In general, the way to learn in this course is to focus +on the IDEAS, not on the SYNTAX. Don't think: "Message passing means +that you say (lambda (message) ...) somewhere." Instead think: +"Message passing means that the data objects in the system know how +to carry out operations on themselves." + + +Some people either didn't read or didn't understand the sample exams +in the course reader. Here is a quote from the spring 1995 solutions: + + *** RESPECTING THE DATA ABSTRACTION DOES **NOT** MEAN SAYING "DATUM" + *** WHENEVER YOU MEAN CAR, AND "CHILDREN" WHENEVER YOU MEAN CDR!! That + is precisely DISrespecting the data abstraction! Respecting it means to + distinguish between a Tree, whose component parts are called datum and + children, and other data types that have other component parts, such as + forests (car and cdr, since a forest is just a particular kind of + sequence), rational numbers (numer and denom), and so on. + +The same thing is true here, except that instead of Trees, this problem +used tagged data. RESPECTING THE DATA ABSTRACTION DOES **NOT** MEAN +SAYING "TYPE-TAG" WHENEVER YOU MEAN CAR, AND "CONTENTS" WHENEVER YOU MEAN CDR! +That is precisely DISrespecting the data abstraction! Respecting it means +to distinguish between a type-tagged datum, whose component parts are +called type-tag and children, and other data types that have other component +parts, such as segments, frames, and vectors. + + +Scoring: + +3 Correct. + +2 The structure of the COND correct, and also + (a) both algorithms work, but have data abstraction violations, or + (b) one algorithm is correct, and there are no DAVs. + +1 At least one working algorithm. + +0 Other. + + +4. Maximum path in Tree + +(define (maxpath tree) + (if (null? (children tree)) + (datum tree) + (+ (datum tree) + (biggest (map maxpath (children tree)))))) + +Notice that there is no CAR or CDR in this program! + +If you didn't want to use MAP, the equivalent recursive solution is + +(define (maxpath tree) + (if (null? (children tree)) + (datum tree) + (+ (datum tree) + (maxpath-forest (children tree))))) + +(define (maxpath-forest forest) + (if (null? (cdr forest)) + (maxpath (car forest)) + (max (maxpath (car forest)) + (maxpath-forest (cdr forest))))) + +This solution does take the CAR and the CDR of a forest (which is +a sequence of Trees), but still does not apply CAR or CDR to a Tree. + +In either case, the algorithm is to find the maxpath of each child, +take the biggest of those, and add the value at the root. So, for +the example in the exam, the maxpath values for the three children +are 10 (7+3), 11 (2+9), and 10 (4+6). The biggest of those is 11, +so we add 5 to that and the overall answer is 16. + +It doesn't work to find the largest immediate child of the root +and work downward from there. In this example, the largest of the +children is 7, the first child, but the largest overall path doesn't +go through that child. + + +PLEASE don't ever try to solve a tree problem iteratively! Iteration +is good for sequences of information -- that is, for one-dimensional +structures. But tree problems are fundamentally recursive. A lot of +solutions had the form + +(define (maxpath tree) + (maxpath-helper tree (children tree) tree '() '() 0 (datum tree))) + +or some similar thing with zillions of extra arguments. All such +solutions turned out to be quite wrong, and what's worse, they take +a long time for us to grade! :-( + + +Here's another correct solution that some people tried: + +(define (maxpath tree) + (biggest (maxpath-helper tree))) + +(define (maxpath-helper tree) + (if (null? (children tree)) + (LIST (datum tree)) + (map (lambda (t) (+ (MAXPATH t) (datum tree))) + (children tree)))) + +Unfortunately, most people who tried this made two mistakes; one was +to leave out the LIST, using just (datum tree) as the base case, and +the other was to call maxpath-helper instead of the capitalized +MAXPATH above. Both of these errors could be avoided by thinking +about the domains and ranges of the functions involved: + + function argument return + + biggest list of numbers number + maxpath Tree number + maxpath-helper Tree list of numbers + +Since BIGGEST expects a list as its argument, maxpath-helper +must return a list, even in the base case. And since + expects +numbers as arguments, you can't use maxpath-helper to provide +one of the arguments to +, because maxpath-helper returns a list. + + +This was apparently the hardest problem, mainly because people don't +understand the Tree Abstract Data Type. The two parts of a Tree +are its DATUM, which is a number, and its CHILDREN, which is a forest, +that is, a list of Trees. A list of Trees is not a Tree! An expression +such as (maxpath (children tree)) has to be wrong because maxpath +requires a Tree as its argument, not a list of Trees. + + +Scoring: There were so many wrong approaches that I can't possibly +list them all. The general strategy we tried to follow was + +5 correct +3-4 has the idea +1-2 has an idea +0 no idea + +Here are a few common cases: + +4 correct except for the base case +3 recursive call to maxpath-helper as described above +2 (maxpath (children tree)) +2 binary tree ADT (e.g., calls to left-branch and right-branch) +1 (biggest (children tree)) with no recursion + + +5. Debugging the broken EVAL-1. + +Of the six test cases given, the four that don't give error messages +give the correct answer; it's the two that say ERROR that are wrong. +What do those two have in common? A compound expression -- a procedure +call -- is used as an argument to another procedure. + +(In the first case, the expression (* 2 2) provides an argument to +; +in the second, the expression (+ 1 1) provides an argument to the +procedure created by the lambda expression.) + +So there's something wrong with the evaluation of argument subexpressions. +That evaluation of subexpressions happens on line 11. The correct line is + + (map eval-1 (cdr exp)) )) ; closing earlier open parentheses + +The reason some of the test cases *do* work is that numbers are +self-evaluating, so using the argument expressions instead of the argument +values doesn't matter if the argument is just a number. The student said + + (cdr exp) )) ; This is what you should have in your solution. + +leaving out the MAP EVAL-1 part. + +The most common error was to say that the error was + + (eval-1 (cdr exp)) )) + +omitting just the MAP. But that would be a disaster; none of the examples +would have worked. Take the first test case: (+ 2 3). If that's EXP, +then (CDR EXP) is (2 3). But if we try to EVAL-1 that list, we are asking +to invoke the procedure 2 with the argument 3! + +By the way, the reason the last test case doesn't fail is that IF is a +special form, so eval-1 never reaches line 11; the subexpressions are +evaluated on lines 6-8. + +Scoring: 5 if correct, 2 if line 11 changed incorrectly, otherwise 0. +(But in the rare cases where the correct change was attributed to line +10 or 12, we figured you just misread the line numbers and didn't take +off points.) We ignored any explanations you gave, which was a good thing +in some cases because the explanations were iffy. + + +6. Data directed programming + +I said at least twice in lecture that data-directed programming does NOT +mean using get and put; the book's example of data-directed programming +is just one example of a more general idea. The idea is that instead of +building the specific details of one problem into our procedures, we +write more general procedures that use some auxiliary data structure to +specify the precise problem we're supposed to solve. In this case, the +list of transitions ((1 A 2) (1 B 3) ...) is the data structure that +tells our GENERAL fsm interpreter which SPECIFIC fsm we're using. + +To make that clearer, here is a program for the particular fsm used as +the example in the question, NOT using data-directed programming: + +(define (transition state letter) + (cond ((= state 1) (state1 letter)) + ((= state 2) (state2 letter)) + ((= state 3) (state3 letter)) + ((= state 4) (state4 letter)) )) + +(define (state1 letter) + (cond ((eq? letter 'A) 2) + ((eq? letter 'B) 3) + ((eq? letter 'C) 4) + (else 0) )) + +(define (state2 letter) + (cond ((eq? letter 'A) 1) + (else 0) )) + +... and so on for the other two states. This program has the specific +transition information built into its procedures. If you wanted to +change a transition, you'd have to rewrite some procedure. Some people +did in fact offer solutions like this, and got no credit. Here is the +solution we had in mind: + +(define (transition fsm state letter) + (cond ((null? fsm) 0) + ((and (= state (caar fsm)) + (eq? letter (cadar fsm)) ) + (caddar fsm) ) + (else (transition (cdr fsm) state letter)) )) + +(define (process fsm state wd) + (if (empty? wd) + state + (process fsm (transition fsm state (first wd)) (bf wd)) )) + +This program works not only for the particular fsm diagrammed in the +question, but for ANY fsm, if we give it the appropriate list of +transitions as an argument. + +For some reason that I don't understand, practically everyone returned +(cddar fsm) instead of the correct (caddar fsm). You want the third +ELEMENT of the transition sublist, not a SUBLIST of the transition sublist. +But we didn't take off for that. + +It's perfectly fine if you want to avoid things like "caddar" (pretty hard +to work through, isn't it?) by defining an abstract data type for +transitions. But please don't think that "data-directed programming" +MEANS using abstract data types. The two ideas are quite distinct, even +though we talked about tagged data during the same week as ddp. If +you want to use an abstract data type your program will look like this: + +(define start-state car) +(define arrow-label cadr) +(define end-state caddr) + +(define (transition fsm state letter) + (cond ((null? fsm) 0) + ((and (= state (start-state (car fsm))) + (eq? letter (arrow-label (car fsm)) ) + (end-state (car fsm)) ) + (else (transition (cdr fsm) state letter)) )) + +You could also define selectors like first-transition and rest-transitions +for the fsm list itself, but I wouldn't bother. Car and cdr are clear +enough for a sequence of any number of the same kind of thing, such as a +sequence of transition triples. + +But, speaking of data types, it won't work at all to use car and cdr on +the word we're processing in part B! Car and cdr only work on pairs +(and lists, which are made of pairs), not on words. + +It would indeed be possible to use GET and PUT to implement a data-directed +fsm program. You'd set up the program for a particular fsm by PUTting each +transition, with the start state and letter as the row and column labels, +and the end state as the contents of each cell. This isn't exactly what we +asked for, but we gave full credit if you did that properly. But we gave +no credit at all if you tried to invoke the contents of the cell as a +procedure! If you did that, you were just blindly copying the example from +the book without understanding it. + +Scoring: Having the idea in part A meant using the fsm list to write a +general program. No credit if the letters A, B, and C appeared in your +program (not data directed) nor if you invoked something you found in a +table (totally off the wall). Having the idea in part B meant using the +procedure you wrote in part A! People who tried to do part B from scratch +invariably wrote programs that CDRed down the fsm list once, then lost it +and couldn't process the second letter. If you got part A completely right +but totally messed up part B, that was three points. The other way around +was two points. If you partially messed up both parts, we used our +judgement in accord with the standard five-point formula. + + +7. OOP + +(a) Parents and children. A child class is /a kind of/ the parent class, or +/a specialization of/ the parent class, /not/ a part or subset of the parent. + +Is a keypad a kind of cell phone? NO, a keypad is part of a cell phone. + +Is an office building a kind of building? YES. + +Is a staple a kind of stapler? NO, it's something you put into a stapler. + +Is an arm bone a kind of arm? NO, it's part of the arm. + +Is an arm bone a kind of bone? YES. + +Is an arm bone a kind of person? NO, it's part of a person. + +(b) Class or instance variable. It's a class variable if it's the same for +every instance of the class; it's an instance variable if each instance has +its own value. + +The number of taxis in the city isn't different for each taxi; it's a property +of the entire CLASS of taxis. + +The number of milk cartons in a fridge is different for each fridge; mine has +quite a few because my son and I can't agree about whether to use fat-free +milk or high-fat (2%) milk, so we get both kinds. A fridge in a photographic +studio might be full of film, and have no milk cartons at all. So the number +is different for each INSTANCE of the fridge class. + +Scoring: 1/2 point each, rounded down to an integer. diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-3.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-3.pdf new file mode 100644 index 0000000..47a822a --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-3.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-1.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-1.pdf new file mode 100644 index 0000000..e79cafe --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-1.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-1.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-1.soln.txt new file mode 100644 index 0000000..174ff1a --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-1.soln.txt @@ -0,0 +1,526 @@ +CS 61A Solutions to sample midterm 3 #1 + +1. Box and pointer. + +(let ((x (list 1 2 3))) + (set-car! x (list 'a 'b 'c)) + (set-car! (cdar x) 'd) + x) + +((a d c) 2 3) is printed. + +X-->[o|o]-->[o|o]-->[o|/] + | | | + | V V + | 2 3 + V + (o|o)-->{o|o}-->[o|/] + | | | + V V V + a d c + +The result of the first set-car! is ((a b c) 2 3); the second set-car! changes +the B to D. (car x) is the pair in (parentheses) in the diagram above, so +(cdar x) is the pair in {braces}. + + +(define x 3) +(define m (list x 4 5)) +(set! x 6) +m + +(3 4 5) is printed. + +M-->[o|o]-->[o|o]-->[o|/] + | | | + V V V + 3 4 5 + +The point of this example is that once (list x 4 5) has been evaluated, it +doesn't matter that the 3 came from X; the list contains the values, not the +expressions that produced the values. So the list M doesn't "know" that X's +value is later changed. + + + +(define x (list 1 '(2 3) 4)) +(define y (cdr x)) +(set-car! y 5) +x + +(1 5 4) is printed. + + Y + | + | + V +X-->[o|o]-->[o|o]-->[o|/] + | | | + V V V + 1 5 4 + +In this example, Y names the same pair as (cdr x). So changing the car of Y +changes the cadr of X, replacing (2 3) with 5. + + + +(let ((x (list 1 2 3))) + (set-cdr! (cdr x) x) + x) + +(1 2 1 2 1 2 1 2 ... is printed. + + +---------+ + | | + V | +X-->[o|o]-->[o|o] + | | + V V + 1 2 + +This example creates a circular list. + + +Scoring: One point per printed representation; one point per diagram. + + + +2. Local state. + +If we call PREV several times, each of the resulting procedures remembers +its own previous invocation. In OOP terminology, PREV represents a class, and +SLOW-SQUARE is an instance of the class. So OLD-RESULT should be an instance +variable. + +Of the four choices offered, the first is the one in which OLD-RESULT is an +instance variable, because the LET happens once per call to PREV, i.e., once +for each instantiation of the class. + +In the second choice, the LET happens only once, when PREV is defined, so +OLD-RESULT would be a class variable. In the third choice, the LET happens +every time an *instance* (such as SLOW-SQUARE) is called, so it's not a state +variable at all, and SLOW-SQUARE would always return #F. + +In the fourth choice, PREV doesn't take an argument! So that can't be right, +and you don't even have to look at the LET. + +Scoring: 4 points, all or nothing. + + +3. Environment diagram. + +There are four frames (including the global one) and three procedures +in the diagram. + +In the global frame, X is bound to 4, BAZ is bound to procedure P1, +and FOO is bound to procedure P3. + +Frame E1 extends the global environment. In it, X is bound to 30 +and * is bound to procedure P2. + +Frame E2 extends E1. In it, Y is bound to 8. + +Frame E3 extends E1. In it, A is bound to 30, and B is bound to 8. + +Procedure P1 is created in the global environment with parameter X +and body (define ...) (lambda ...) + +Procedure P2 is created in E1 with parameters A and B, and body (+ a b). + +Procedure P3 is created in E1 with paremeter Y and body (* x y). + +--------- + +The first expression just adds the X binding to the global environment. + +The second expression creates P1 and binds BAZ to it in the global +environment. + +The third expression invokes BAZ, so it creates E1 with X bound to 30. +[A common error was to bind X to 13, thinking that * means addition +in the expression (* 3 10). But procedure P2 hasn't even been created +yet when (* 3 10) is evaluated, let alone the fact that this expression +is evaluated in the global environment because it was typed at a Scheme +prompt.] Then it evaluates the body of BAZ in environment E1. This +creates P2, binds * to it in E1, creates P3, and returns P3 as the +value from BAZ. Then FOO is bound to that value, P3, in the global +environment. + +The fourth expression computes (* 2 x) in the global environment, +getting 8, and creates E2 with Y bound to 8. [A common mistake was +to use the value 30, in E1, for X and also use P2 for *, thereby +computing the value 32 for Y.] Then, with E2 as the +current environment, it evaluates the body of FOO, which is (* x y). +Since E2 is the current environment, and it extends E1, the symbol * +represents procedure P2 in this expression. Since this is a +user-defined procedure, not a primitive, this creates E3 with A +bound to 30 (the value of X found in E1) and B bound to 8 (the value +of Y found in E2). Then (+ a b) is evaluated in E3, returning the +value 38, which is the value of the entire expression. + +--------- + +Scoring of common mistakes: + + 3 correct + + 2 correct return value 38, but... + E3 extends E2 + E3 variables are named X and Y instead of A and B + E3 binds A to "X" instead of 30 and B to "Y" + E3 left out altogether + P3 right bubble points to E2 + + 1 X=13 in E1 + Y=32 in E2 + E2 extends global environment + In E1, "(* a b)" is bound to "(+ x y)" + The third expression is interpreted as if it were + (define (foo) (baz (* 3 10))) + thereby making FOO a procedure of no arguments that calls BAZ + + 0 P3's right bubble points to the global frame + E1 extends E2 (very strange sequence of events!) + Y=30, as if it were + (define (baz y) (* x y)) + extra/missing frames or procedures except as noted earlier + several errors + + +4. List mutation. + +The easiest way to do a problem like this is to use a LET in which +you give names to every relevant piece of the list structure. Then, +inside the LET, you can mutate the pairs in any old order without +risk of error: + +(define (make-alist! lst) + (if (null? lst) + 'done + (let ((car1 (car lst)) + (cdr1 (cdr lst)) + (car2 (cadr lst)) + (cdr2 (cddr lst))) + (set-car! lst cdr1) + (set-cdr! lst cdr2) + (set-car! cdr1 car1) + (set-cdr! cdr1 car2) + (make-alist! cdr2))) + lst) + +But that's more work than is really needed. If you're clever about +the order in which you do the mutation, you can get by with only one +temporary variable. There are several such solutions; here's one: + +(define (make-alist! lst) + (if (null? lst) + 'done + (let ((tmp (cddr lst))) + (set-cdr! (cdr lst) (cadr lst)) + (set-car! (cdr lst) (car lst)) + (set-car! lst (cdr lst)) + (set-cdr! lst tmp) + (make-alist! tmp))) + lst) + +Both of these solutions use the original first pair as the top-left pair +of the resulting association list; the original second pair becomes the +bottom-left pair. Several people noticed that you can rearrange the +pairs with no temporary variables at all if you reverse those roles, +so that what used to be the second pair becomes the head of the new +association list. Unfortunately, this isn't quite a correct solution, +because the caller of MAKE-ALIST! probably has some variable that still +has the original first pair as its value, so the caller will think that +that first pair is the new a-list. + +Neither of these solutions uses the value returned by recursive calls. +It's also possible to write a solution that does: + +(define (make-alist! lst) + (if (null? lst) + 'done + (let ((tmp (make-alist! (cddr lst)))) + (set-cdr! (cdr lst) (cadr lst)) + (set-car! (cdr lst) (car lst)) + (set-car! lst (cdr lst)) + (set-cdr! lst tmp))) + lst) + +Note that you must check (NULL? LST) *before* you try to take its +CAR or CDR. + +Scoring of typical solutions: + +4 OK +3 Bad/missing base case; + rearranges by mutation but the order isn't quite right; + leaves second pair on top; + uses return value from recursive call but doesn't return a value. +2 No temporary variable (via LET or helper procedure). +1 Uses CONS (or LIST or APPEND, etc). +0 (set! (car lst) ...) or similar confusions. + +Solutions using CONS scored lower than other errors because the problem +explicitly said not to allocate new pairs. It's important that you +understand the difference between allocating a pair and making a new +pointer to an already-existing pair. Although it's true that the old +pairs would be reclaimed, so the total storage requirement of the program +wouldn't increase with solutions using CONS, sometimes it's important not +to allow a delay for garbage collection. For example, if your program is +creating video animation in real time, a garbage collection might bring +the animation to a halt for a substantial time, perhaps half a second. + + +5. Vectors. + +To solve this problem it's important to understand what it's about. The +result (histogram) vector is separate from the argument (scores) vector; the +two vectors have different sizes; there is no simple correspondence between +one element of the result and one element of the argument. Each element of +the result depends on examining *every* element of the argument. The kind of +higher order function strategy that we often use for lists is not appropriate +in this problem. + +Having passed that hurdle, there is an insight about algorithms that helps +to simplify the solution if you see it: Although each element of the result +depends on every element of the argument, each element of the *argument* +contributes to *only one* element of the result. Therefore, a solution that +works by iterating through the elements of the argument can run in Theta(N) +time, whereas a solution that iterates through the elements of the result +will require Theta(N^2) time, and more complicated code. + +Here is the Theta(N) solution: + +(define (histogram scores) + (define (help result i) + (if (< i 0) + result + (begin (vector-set! result + (vector-ref scores i) + (+ (vector-ref result (vector-ref scores i)) 1)) + (help result (- i 1))))) + (help (make-vector (+ (vector-max scores) 1) 0) + (- (vector-length scores) 1))) + +It's important that the call to MAKE-VECTOR initializes every element of the +histogram vector to zero, because we're going to be adding to those values in +the HELP loop. + +You might find it easier to read this slight variant: + +(define (histogram scores) + (define (help result i) + (if (< i 0) + result + (let ((score (vector-ref scores i))) + (vector-set! result + score + (+ (vector-ref result score) 1)) + (help result (- i 1))))) + (help (make-vector (+ (vector-max scores) 1) 0) + (- (vector-length scores) 1))) + +Here's the Theta(N^2) version: + +(define (histogram scores) + (define (count-score score total j) + (cond ((< j 0) total) + ((= (vector-ref scores j) score) + (count-score score (+ total 1) (- j 1))) + (else + (count-score score total (- j 1))))) + (define (help result i) + (if (< i 0) + result + (begin (vector-set! result + i + (count-score i 0 (- (vector-length scores) 1))) + (help result (- i 1))))) + (help (make-vector (+ (vector-max scores) 1)) + (vector-max scores))) + +And, yes, instead of writing COUNT-SCORE as above, you could use +(VECTOR-LENGTH (VECTOR-FILTER ...)) to find the count of students with a +given score. But that would be pretty inefficient (although only by a +constant factor), because VECTOR-FILTER examines every element of the +argument vector twice, and creates a new vector, which you use only long +enough to count its elements, then throw it away. VECTOR-FILTER makes a good +homework problem, but it's not something you would ever really want to use in +vector-based programming. + +It's possible to use the Theta(N^2) algorithm with only one helper procedure, +instead of two, by having the helper take two index arguments, one for each +vector. But it's really, really hard to get that right, and even if you do, +it's really, really hard for anyone else (or you, next week) to read the +resulting program. + + +The first index in a vector is 0; the last is (- (vector-length vec) 1). +Many people lost a point by trying + (vector-ref vec (vector-length vec)) + +People found many ways to make the problem more complicated than necessary, +such as using + (define (helper i) + ... + (set! i (+ i 1)) + (helper i)...) +instead of + (define (helper i) + ... + (helper (+ i 1))...) +This isn't incorrect, but at this late stage in the semester it shows an iffy +understanding of recursion. + +The only two places you can use DEFINE are at the Scheme prompt or at the +beginning of a procedure body. You can't, for example, say + (cond (some-test + (define ...) + ...) + ...) + + +Scoring: + +7 correct. + +6 off-by-one error in calculating vector length or end test. + +5 in Theta(N) algorithm, doesn't initialize result elements to zero. +5 computes vector correctly but doesn't return it. +5 right logic, but a Scheme language error (e.g., misplaced DEFINE). + +4 (VECTOR-REF RESULT INDEX) instead of + (VECTOR-REF RESULT (VECTOR-REF SCORES INDEX)). + +2 No allocation of new vector (result overwrites argument). + +0 Uses lists, or takes car/cdr of a vector. + +There were other, less common errors; generally "has the idea" got 5, while +"has an idea" got 2. + + +6. Parallelism in real life. + +For this question we got several essays trying to justify solutions other +than the obvious ones. For the most part we didn't accept these -- the +problem did say "the answer which BEST describes..." -- with one exception +noted in part (b) below. + +(a) People at tables can't get food; people waiting for food can't get +tables. This is a potential deadlock, and that was the answer we wanted. +It's true that the deadlock might not happen, because some people at +tables may actually have food and might eventually leave, letting the line +continue moving. It depends partly on whether the restaurant servers +believe you when you say "it's okay to serve me because my friend is already +sitting at a table and saving me a seat." Even if they do, a deadlock can +happen if someone comes in alone (so doesn't have a friend to grab a table) +and when that person gets to the front of the line, all the tables are filled +with friends of people behind him/her in line. + +You may think "it's UNFAIR for people who don't have food yet to hog the +tables" or "it's INEFFICIENT for people to sit at tables when they don't +have food yet." But these are technical terms about parallellism errors, +and the particular situation described in the problem is technically a +deadlock. + +(b) There are several inspectors serving several lines in parallel, but +there's only one metal detector, which acts as a single serializer for +all the inspectors. This is inefficiency (too much serialization). + +Some people argued that the metal detector is best viewed as an actual +resource, not as a serializer, and so this is correct, if unfortunate, +serialization of a shared resource. We accepted that reasoning, so we +also accepted "none of the above" as a correct answer. + +(c) You write while your friend researches. This is correct parallelism, +with two processors carrying out parallelizable tasks. + +Some people argued that the tasks *aren't* correctly parallellizable +because the research has to come before the writing. That idea has some +merit for a short paper, but you wouldn't be writing a short paper as a +team anyway; it'd be an individual assignment. We meant that you were +writing one part of the paper while your friend was researching a different +part of the paper. + +Some people said "unfairness" because you have to do the boring writing +while your friend is off doing the interesting research. One of the +nice things about working in groups is that sometimes you're lucky and +your interests complement those of your friend! But even if you would +feel an unfairness in this arrangement, it's not unfair in the technical +sense -- a parallelism unfairness would be if the librarians always get +books for your friend before they get books for you. + +Scoring: One point each. + + +7. Streams. + +The easiest solution is in two steps: First we make a stream of all possible +strings of {\tt OVER} and {\tt UNDER}, and then we filter out the ones that +don't satisfy the condition of having at least one of each: + +(define foo + (cons-stream '() + (interleave (stream-map (lambda (p) (cons 'over p)) foo) + (stream-map (lambda (p) (cons 'under p)) foo)))) + +(define patterns + (stream-filter (lambda (p) (and (member 'over p) (member 'under p))) + foo)) + +You can't combine these two steps; several people tried this: + +(define patterns ;;; wrong! + (stream-filter (lambda ...) + (cons-stream '() (interleave (stream-map ... patterns) + (stream-map ... patterns))))) + +The trouble is that this process will never get started, because the two calls +to stream-map can only operate on patterns that have previously been +generated, and there won't be any of those until something makes it through +the filter. As a result, the variable PATTERNS hasn't been defined when the +calls to stream-map try to use it. + +Another wrong solution was to try to avoid the need for filtering by "priming +the pump" with initial patterns other than the empty one, like this: + +(define patterns ;;; wrong! + (cons-stream '(over under) + (cons-stream '(under over) + (interleave ...)))) + +This indeed gets started correctly, and generates only legal patterns, +but it doesn't generate all of them. In particular, it won't generate +the example shown in the problem: + + (over over under over under under) + +because this pattern, although legal, doesn't end with OVER UNDER or +UNDER OVER. + +Some people, recognizing the problem with that last solution, tried to +get around it by adding words both front and back. That might possibly +work, but the people who tried it wanted to add words at the end with + (cons p 'over) +which of course doesn't make a valid list. + +Another intriguing method involved the use of random numbers to make +a randomly chosen pattern for each element of the stream. It can be +argued that if the random number generator has perfectly well-distributed +results, this approach will eventually generate any desired pattern. +(And, since the number of already-generated patterns is finite, and +the number of not-yet-generated patterns is infinite, the probability +of duplication of patterns is zero! Alas, this doesn't mean it can't +happen. :-) But we didn't accept these solutions because part of the +idea in an infinte stream is that you have to be able to guarantee that +any particular element is reachable in bounded time. + + +Scoring: We graded this one very leniently: + +3 correct +2 interleave correct, filtering missing or incorrect +1 interleave wrong, but a good try +0 not close diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-2.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-2.soln.txt new file mode 100644 index 0000000..759cb3b --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-2.soln.txt @@ -0,0 +1,484 @@ +CS 61A Solutions to sample midterm 3 #2 + +1. Box and pointer. + +(let ((x (list 1 2 3))) + (set-cdr! (car x) 4) + x) + +prints: *** Error: + set-cdr!: wrong type of argument: 1 + +(CAR X) is 1, not a pair, so it has no cdr to mutate. + + +(let ((x (list 1 2 3))) + (set-cdr! x 4) + x) + +(1 . 4) is printed. + +X-->[o|o]--> 4 + | + V + 1 + +Since we are changing the list's cdr to a non-pair, it becomes a "dotted pair." + + +(let ((x (list 1 2 3))) + (set-car! (cdr x) x) + x) + +(1 (1 (1 (1 (1 ... is printed. + + + +------+ + | | + V | +X-->[o|o]-->[o|o]-->[o|/] + | | + V V + 1 3 + +The list's second element is replaced with the list itself, making a circular +list. 3 is still the third element, but the print procedure never reaches it. + + +(define a ((lambda (z) (cons z z)) (list 'a))) +(set-cdr! (car a) '(b)) +a + +((a b) a b) is printed. + +A-->[o|o] + | | + | | + | | + | | + V V + {o|o}-->[o|/] + | | + V V + a b + +Note that the two arrows downward from the first pair point to the same place! +An arrow to a pair points to the entire pair, not just to its car or its cdr. +(By contrast, an arrow *from* a pair *does* come from one half of the pair, +not from the entire pair.) + +The pair in {braces} is the one whose cdr is changed (from being the empty +list) by the set-cdr! invocation. + + +Scoring: One point per printed representation; one point per diagram. + + + +2. Assignment, state. + +(define (make-player room) + (lambda (message) + (set! room (next-room room message)) + room)) + +That's it! There's no need to check for specific messages such as South, +since next-room will take care of that for you. + +Scoring: + +4 correct +3 sets room correctly but doesn't return it +2 domain and range of make-player and of the lambda correct, but + something's wrong with setting room. +1 room is set, but no lambda +0 even worse + + +3. Environment diagram. + + +First of all, in this problem there are two procedures created: + +P1: parameters X and F, body (IF ...) + +P2: parameter Y, body (+ X Y) + + +There are also four environment frames: + +G: the global frame + +E1: has X bound to 3, F bound to #F + +E2: has X bound to 5, F bound to procedure P2 + +E3: has Y bound to 7 + + +Solutions not satisfying the above generally got no points. + +The hard part is how to hook these up. When FOO is defined, a binding +for FOO is made in the global environment. Also, the global environment +is current when the (outer) LAMBDA expression is evaluated, so FOO is P1 +and P1's right bubble points to G. + +By the way, that first expression could have been written as + + (define (foo x f) ...) + +with exactly the same meaning. + +That's all that happens when the first expression is evaluated. +Procedure P2 and frames E1 through E3 are all created during the +evaluation of the second expression. + +First we call FOO with arguments 3 and #F. This creates frame E1, +which extends G, because G is what P1's right bubble points to. + +Now we evaluate the body of P1 (a/k/a FOO), using E1 as the current +environment. The body is the IF expression. F is false, so we must +evaluate (FOO 5 (LAMBDA ...)). + +To evaluate a procedure call we first evaluate all the subexpressions. +In particular, the inner LAMBDA expression is evaluated at this time, +with E1 as the current environment. Therefore, P2's right bubble +points to E1. + +Once we've evaluated the subexpressions, we create a new frame, E2, +binding FOO's parameters to these new arguments. So in E2 the value +of X is 5, and the value of F is procedure P2. Note that this +binding for F is in E2, but the procedure to which F is bound was +created in E1. That's really important, and many groups missed it. + +What environment does E2 extend? Since we are calling P1 (a/k/a FOO), +we extend the environment in P1's right bubble, namely G. This, too, +is a really important point. If you had E2 extend E1, you are using +dynamic scope, not lexical scope, which is correct for Scheme. + +We now evaluate the body of P1, the IF expression, with E2 current. +The value of F is true in this environment (since anything other than +#F is considered true), so we now evaluate (F 7). + +To do that, we make a frame, E3, in which Y is bound to 7. What environment +does E3 extend? The procedure we're calling, P2, was created in E1, so E3 +must extend E1 -- not E2, even though that's the current environment. + +Since E3 extends E1, the relevant value of X is 3, and so the answer +that Scheme prints is 10, which is 3+7. + +The most common wrong answer was 12, which is 5+7. (Only a handful of +papers had any answer other than 10 or 12.) As it turns out, there were +two ways of getting the answer 12, with different scores: + + * Many groups thought that procedure P2 was created in environment E2, + and so E3 would extend E2 even following the lexical scope rule. + This was a relatively mild error, getting 2 points. + + * Many other groups used dynamic scope, getting 1 point. You were + deemed to be using dynamic scope if E3 extended E2 even though P2's + right bubble pointed to E1. You were also deemed to be using + dynamic scope if E3 extended E2, and E2 extended E1, regardless of + where P2 pointed. + + (A few papers had E2 extending E1, but E3 correctly extending E1, + the diagram otherwise correct, and an answer of 10. These groups + were not deemed to be believers in dynamic scope, but merely + careless, getting 2 points.) + +Several groups got the answer 10 despite incorrect diagrams. This was a +surprise, but it turned out that they did it by mixing the substitution +model with the environment model. (Since the expressions in the problem +did not involve mutation, the substitution model does yield the right +value for (FOO 3 #F) even though it's not what Scheme really does.) +More specifically, these solutions had (+ 3 Y) instead of (+ X Y) as the +body of P2. Such papers got 1 point. + +Some papers had P2's right bubble pointing to E3, a frame that didn't +even exist when P2 was created. We don't understand what those groups +were thinking. + +Another zero-point solution was to have bindings to expressions rather +than to values. For example, some papers had a binding in E2 of the form + + F: (lambda (y) (+ x y)) + +It's really important to understand that Scheme's job is to translate +expressions into values, and that only values get into environments. +(This is what it means to say that Scheme uses applicative order +evaluation, rather than normal order.) + +Scoring: + +3 OK +2 lexical scope, but some error +1 dynamic scope, or substitution model +0 gibberish, extra frames, expressions in environments + + +4. List mutation. + +We were surprised at how hard you found this problem. The solution +we wanted is pretty short and simple: + +(define (merge! a b) + (cond ((null? a) b) + ((null? b) a) + ((<= (car a) (car b)) + (set-cdr! a (merge! (cdr a) b)) + a) + (else + (set-cdr! b (merge! a (cdr b))) + b))) + +This solution DEPENDS CRITICALLY on the fact that merge! RETURNS A VALUE. +Most of you got in trouble by forgetting to return a value. + +The easiest way to think about this problem may be to start by writing +a functional (non-mutating) version: + +(define (merge a b) ; Not a solution to the exam problem! + (cond ((null? a) b) + ((null? b) a) + ((<= (car a) (car b)) + (cons (car a) (merge (cdr a) b))) + (else + (cons (car b) (merge a (cdr b)))))) + +There's a stream version of this procedure in the book, and in any case +you should find it easy to invent this. The mutating version has the +SAME STRUCTURE, but instead of calling CONS it has to mutate an +existing pair, and separately return a value. + +One of the most important ideas you can learn is the mathematical +concept of SYMMETRY. In this case, what that means is that you should +notice that merge! treats its two arguments equivalently; if you +interchanged the order of the arguments you should still get the same +answer. Therefore, your program should be symmetrical as well; anything +you do to A should be done in the same way to B. Many people used +asymmetrical kludges, and therefore had incredibly long programs that +didn't work. + +Another good idea to learn is QUIZMANSHIP. Some time around your +11th or 12th cond clause, you ought to stop and think, "They wouldn't +assign something this complicated on an exam." (This is quite +different from the sort of quizmanship in which you try to guess at +answers based on irrelevant factors.) + +Several solutions had cond clauses with complicated conditions such as + (and (< (car a) (car b)) (> (car a) (cadr b))) +There are a few situations in which you really do have to use this +degree of complexity, but they're rare. Really what this means is +that you're not trusting the recursion to do its job with the second +elements of the lists. + +Several solutions rearranged things in a way that would work only if +the second-smallest number is in the other list from the smallest +number. That is, you hook the two cars together and then recursively +deal with the two cdrs. Think about a case like + (merge! (list 1 2 3) (list 4 5 6)) +In this example the result should be the same as if you'd appended +the lists, not the same as if you interleaved them. + +A few people did append the lists, and then sort them by insertion +sort or bubble sort or some such thing. This can work, and we +gave full credit for working solutions of this kind, but you should +be aware that it makes the problem take O(n^2) time instead of +O(n), and it's more complicated to write correctly, too! By +appending the two lists you're losing the valuable information +that each of them is already ordered. + +In a problem about lists, you have to remember that the car and +the cdr of a pair do NOT play symmetrical roles in the representation +of a list. Each car is an element; each cdr is a sublist. In a +list of numbers, each car is a number; no cdr is a number. Therefore, +any solution that interchanges cars and cdrs or tries to mutate a +car of something just can't be right: + (set-car! (car x) ...) + (set-cdr! (car x) ...) + (set-cdr! x (car y)) + (set-car! x (cdr y)) +For solutions of this sort we subtracted three points from what +the score would otherwise be. + +Grading: +7 correct +6 base case error +5 no return value, but it only matters to the ultimate caller +4 no return value, and so the recursion doesn't work +4 rearranges pairs with set-cdr! but incorrectly +3 +2 uses set-car! to rearrange pairs. (Some set-car! solutions are correct.) +1 +0 allocates pairs (calls CONS, LIST, APPEND, etc.) +0 uses set! to rearrange pairs. (Some uses of set! are okay, but they + never actually help the solution.) + +Then subtract 3 points for the cases mentioned in the previous paragraph. + + +5. Vectors. + +There are many ways to do this, but they all share two essential points: +First, there must be a helper procedure that recursively moves through the +vector, changing one element at a time; second, there must be some way to +remember one element (generally the original last element) of the vector, +either through a LET or through an extra argument to the helper. + +Here's a straightforward solution: + +(define (rotate! v) + + (define (help i) + (if (= i 0) + 'this-value-doesnt-matter + (begin (vector-set! v i (vector-ref v (- i 1))) + (help (- i 1))))) + + (let ((temp (vector-ref v (- (vector-length v) 1)))) + (help (- (vector-length v) 1)) + (vector-set! v 0 temp) + v)) + +The last line (with just the V) is there so that ROTATE! returns the vector, +since the return value from VECTOR-SET! is unspecified. + +The elements of a vector of N elements are numbered from 0 to N-1, not from +1 to N. That's why the expression (- (VECTOR-LENGTH V) 1) is used to find +the index of the rightmost element. + +It's very important that this program starts at the right end and works +down to the left end, so that if we are given (A B C D) to rotate, the +intermediate results are + (a b c d) + (a b c c) + (a b b c) + (a a b c) + (d a b c) +If we started at the left end instead, we'd get + (a b c d) + (a a c d) + (a a a d) + (a a a a) ; maybe stop here, or + (d a a a) ; maybe something like this. +There are other ways to organize the program so that left-to-right operation +does produce the desired result. Here's one that works from left to right, +always swapping the chosen element with the last element: + +(define (rotate! v) + + (define (swap v i j) + (let ((temp (vector-ref v i))) + (vector-set! v i (vector-ref v j)) + (vector-set! v j temp))) + + (define (help i) + (if (< i (vector-length v)) + (begin (swap v i (- (vector-length v) 1)) + (help (+ i 1))))) + + (help 0) + v) + +When we ran across this solution in the grading, it took us some time to +convince ourselves that it really works. Here's a trace of intermediate +results: + (a b c d) + (d b c a) + (d a c b) + (d a b c) + (d a b c) + +The problem told you to mutate the given vector, not create a new one. +That rules out any call to MAKE-VECTOR, either directly or through a +helper procedure such as VECTOR-COPY; it also rules out things like + (list->vector (list-rotate (vector->list v))) + +A few students recognized that they should use a LET to save something, +but instead of saving one element, tried to save the entire vector with +something along the lines of + (let ((new-v v)) ...) +If this did what they intended, it would be ruled out by the problem +statement, but in fact it does *not* make a copy of the vector. It just +makes a new variable that's bound to the same (as in EQ?, not EQUAL?) +vector as the original variable V. + + +Scoring: + +7 correct. + +6 indexing off by one (1 to N instead of 0 to N-1). + vector rotated, but not returned. + +4 one element lost (no LET or equivalent). + new vector allocated, but no VECTOR->LIST or LIST->VECTOR. + no base case in recursive helper. + one value propagated by shifting left-to-right. + +2 LIST->VECTOR etc. + no recursion (just two values swapped). + other messed up reorderings (such as reversal). + +0 Total misunderstanding of vectors, such as (CAR V). + +We did not assign scores 1, 3, or 5. + + +6. Concurrency. + +(a) The only possible value is 10. If the first process runs first, +it sets BAZ to 5, and then the second process sets it back to 10. If the +second process runs first, it sets BAZ to 20, and then the first process +sets it back to 10. + +(b) 5: P1 computes baz/2 = 5, then P2 runs completely, then P1 stores 5. + 10: either correct sequential order + 15: P2 loads BAZ once from memory (getting 10), then P1 runs + completely (setting BAZ to 5), then P2 loads BAZ again + (getting 5), adds 10+5, stores 15. + 20: P2 computes baz+baz = 20, then P1 runs completely, then + P2 stores 20. + + +Scoring: + +3 correct +2 (a) correct, (b) missing one value and no wrong ones added +1 (a) correct or (b) correct +0 neither correct + + +7. Streams. + +(define stream-car car) ; unchanged from the stream-only version + +(define (stream-cdr sl) + (if (procedure? (cdr sl)) ; or PROMISE? + (force (cdr sl)) + (cdr sl) )) + +;;;;;;;; or + +(define (stream-cdr sl) + (if (or (pair? (cdr sl)) (null? (cdr l))) + (cdr sl) + (force (cdr sl)) )) + +Scoring: 1 point for stream-car, 3 for stream-cdr. Part credit in the latter +for any attempt that shows understanding of the need to distinguish the two +cases, especially if it's clear that what needs to be distinguished is the +nature of the cdr rather than of the entire argument. + +Comment: Many of you seem to be upset because you never heard of the +predicate PROCEDURE? and therefore couldn't figure out how to do the +test. I'm unsympathetic to this problem, for several reasons: + + 1. You came across PROCEDURE? in the adventure game project, + where it is used in the version of PERSON? that you rewrote. + + 2. You own a copy of the Scheme reference manual, which has + a perfectly good index. + + 3. If you couldn't think of PROCEDURE? you could have used + PAIR? or ATOM? or LIST? to distinguish the two cases. diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-3.soln.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-3.soln.txt new file mode 100644 index 0000000..20db87b --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-3.soln.txt @@ -0,0 +1,459 @@ +CS 61A Solutions to sample midterm 3 #3 + +1. Box and pointer. + +(let ((x (list 1 2 3))) + (set-cdr! (cdr x) (cddr x)) + x) + +(1 2 3) is printed. + +X-->[o|o]-->[o|o]==>[o|/] + | | | + V V V + 1 2 3 + +In this example the SET-CDR! call effectively does nothing, since it +replaces the cdr of (cdr x) with the cddr -- the cdr of the cdr -- of X. +The arrow drawn with = instead of - above is the one that's replaced with +itself. + + +(let ((x (list 1 2 3))) + (set-car! x (cddr x)) + x) + +((3) 2 3) is printed. + + +----------------+ + | | + | V +X-->[o|o]-->[o|o]-->[o|/] + | | + V V + 2 3 + +The set-car! invocation changes (car x), i.e., the first element of X. +It's changed to (cddr x), which is a *sublist*, not just an element, of X. +Thus the new first element is not 3, but (3). + + + +(let ((x (list 1 2 3))) + (set-car! (cdr x) (cdr x)) + x) +(1 ((((((((( ... is printed. + + +-+ + | | + | V +X-->[o|o]-->[o|o]-->[o|/] + | | + V V + 1 3 + +Note that the arrow at the top of the diagram points *from the car* of the +second pair, but points *to the entire pair* (because that's how pointers +always work), not just to the cdr, even though that's where the arrowhead +happens to be. + +There's still a 3 in this list, but it'll never be printed. + + + +(let ((x (list 1 2 3 4))) + (set-cdr! (cddr x) (cadr x)) + x) + +(1 2 3 . 2) is printed. + +X-->[o|o]-->[o|o]-->[o|o]--> 2 + | | | + V V V + 1 2 3 + +In this example we change the cdr of a pair (because we're doing SET-CDR!) to +point to a non-pair, (CADR X), the second element of X, which is 2. Thus the +result is an improper list, so there's a dot in the printed version. + +It doesn't matter, in the diagram, whether you have two 2s, as above, or have +two arrows pointing to the same 2. It *does* matter when the thing being +pointed to is a pair; then there's a big difference between two pointer to the +same pair, and two pairs that have the same values in them. + + +Scoring: One point per printed representation; one point per diagram. + + +2. Local state. + +Does Louis's MEMOIZE give wrong answers? YES. + +Explanation: It has one table shared among all memoized functions, +instead of a separate table per function. + +Example: + +[Louis has defined MEMO-FIB, as shown in the question.] + +> (memo-fib 4) +3 +> (define memo-square (memoize (lambda (x) (* x x)))) +> (memo-square 4) +3 + +Since MEMO-FIB and MEMO-SQUARE share the same table, (memo-square 4) +returns the value previously remembered from (memo-fib 4). + +Some students who checked NO explained why the answer is really YES, so +we figured people misread the question, and went by your explanantion +rather than by which choice you checked. + +Pretty much any explanation with a phrase like "a single table" or +"universal table" or "global table" was accepted. (It's not quite right +to say "a table in the global environment"; the table is actually a local +state variable of MEMOIZE.) + +Explanations that merely restate the form of Louis's change to the program +were not accepted: "The program gives wrong answers because Louis has moved +the LET to outside of the LAMBDA." You had to explain what *effect* that +would have on the program's *behavior*. + +The example didn't necessarily have to take the form of a specific Scheme +interaction as above, but did have to assert that two different functions are +memoized. + +Scoring: + +4 correct +2 correct explanation, no/bad example; + iffy explanation (like "global environment" discussed above) +0 bad explanation (including saying that it doesn't give wrong answers) + +No odd scores were assigned. + + +3. Environment diagram. + +Bindings A=8 and B=9 go in the global environment. + +Then comes the LET, which is equivalent to an invocation of the procedure +generated by an implicit LAMBDA: + + ((lambda (a f) (f 5)) + 3 + (lambda (b) (+ a b))) + +As with any procedure invocation, **first all the subexpressions are +evaluated!** This evaluation takes place in the global environment -- we +haven't invoked any procedures yet. + +Thus, two procedures are created whose right bubbles point to the global +environment. Only then do we invoke the (lambda (a f) ...) procedure, which +creates a frame in which A is bound to 3, and F is bound to the +(lambda (b) ...) procedure. That new frame, of course, extends the global +environment. + +With that frame as (the first frame of) the current environment, we can +evaluate the body of the LET, which is (F 5). We find a binding for F in +the current environment; it's the (lambda (b) ...) procedure. So we can +invoke that with the argument 5. + +Since F's right bubble points to the global environment, that's what we +extend with the new frame that binds B=5. So when we evaluate F's body, +which is (+ A B), we find the bindings A=8 and B=5. + +Thus, the final answer is 13. + + +The overwhelmingly most common mistake was to think that the (lambda (b) ...) +procedure's right bubble points to the A=3 frame, so the B=5 frame points +there also, and the final value is 8. You should know, though, that a LET +binding can't depend on another binding in the same LET; for example, if the +problem had been + + (let ((a 3) + (c (+ a b))) + (+ a c)) + +I hope most people would have known that C would be 8+9, using the global +bindings for both A and B. The fact that the computation using A happens +inside a lambda body doesn't change the fact that the LET's binding for A +isn't available to it. + +A few people drew the environment diagram that would give an answer of 8, +but instead wrote 13 as their final answer, which means either that they +copied someone else's final answer or that they *do* know how Scheme +evaluates expressions, but don't make any connection between that and +the environment model. We graded this as if they'd said 8. + +A couple of people had procedure F's right bubble correctly pointing to the +global environment, but nevertheless had the B=5 frame extending the A=3 +frame, using dynamic scope instead of lexical scope. This gave the same +wrong final answer of 8. + +Scoring: + +6 correct. +3 answer was (or should have been) 8, as discussed above. +0 even worse (too many frames, no arrows at all -- there weren't many). + + +4. List mutation + +(define a (list 'x)) +(define b (list 'x)) +(define c (cons a b)) +(define d (cons a b)) + +(eq? a b) => #F + + Each call to LIST generates new pairs (one new pair, in this case, + because each list has only one element). + +(eq? (car a) (car b)) => #T + + Both CARs are the symbol X, and equal symbols are always EQ. + +(eq? (cdr a) (cdr b)) => #T + + Both CDRs are the empty list, and there's only one empty list. + +(eq? c d) => #F + + Each call to CONS generates a new pair. + +(eq? (cdr c) (cdr d)) => #T + + Both CDRs are the pair named B -- the same pair. + +(define p a) +(set-car! p 'squeegee) +(eq? p a) => #T + + P and A are two names for the same pair. Mutating the pair + doesn't change the variable bindings. + +(define q a) +(set-cdr! a q) +(eq? q a) => #T + + This one looks trickier because the pair now points to itself, + but it's really the same as the previous question: Q and A are + two names for the same pair. + +(define r a) +(set! r 'squeegee) +(eq? r a) => #F + + This time we didn't mutate a pair; we changed the binding of + one of the variables. So R and A now name two different things; + A is still a pair, but R is now a symbol. + +Score: 1/2 point each, rounded down to the nearest whole point. + + +5. Vector programming + +(define (ssort! vec) + (define (help start) + (if (= start (vector-length vec)) + vec + (let ((smallest (subvec-min-start vec start))) + (let ((temp (vector-ref vec smallest))) + (vector-set! vec smallest (vector-ref vec start)) + (vector-set! vec start temp) + (help (+ start 1)))))) + (help 0)) + +The key point to understand is that you need to walk through the vector, +bringing the smallest element out to position 0, then the next-smallest to +position 1, and so on, until you run out of elements. Thus we have a helper +procedure with an argument, START, whose value is the position that we're +up to in the vector; it starts at 0 and is increased by 1 on each recursive +invocation. + +The next important point is that you can't exchange two elements without +using a temporary variable to remember one of them, hence the LET that +creates the variable TEMP. There are two nested LETs because the value of +SMALLEST is needed to find the value of TEMP in this solution; I could have +simplified things a little by remembering the other value in the swap instead: + +(define (ssort! vec) + (define (help start) + (if (= start (vector-length vec)) + vec + (let ((smallest (subvec-min-start vec start)) + (temp (vector-ref vec start))) + (vector-set! vec start (vector-ref vec smallest)) + (vector-set! vec smallest temp) + (help (+ start 1)))))) + (help 0)) + +Scoring: + +6 correct +5 trivial error (e.g. base case off by one) +3 right structure, gets swap wrong +2 serious algorithm confusion +0 allocates new vector, uses lists, or incoherent + + +6. Concurrency + +(define (make-mutex) + (let ((in-use #f) + (s (make-serializer))) + (define (the-mutex m) + (cond ((eq? m 'acquire) + (if ((s (lambda () + (if in-use + #t + (begin (set! in-use #t) + #f))))) + (the-mutex 'acquire))) ; retry + ((eq? m 'release) + (set! in-use #f)))) + the-mutex)) + +The structure of the above is just like that of the MAKE-MUTEX in the book, +except that when an atomic test-and-set operation is needed, it's done by +including the (IF IN-USE ...) and the (SET! IN-USE #T) within the same +serialized procedure, rather than by relying on a TEST-AND-SET! primitive. + +Many people found the problem deeply confusing. You learned that +serialization has three levels of abstraction: the hardware support, +the critical section mechanism (mutex) based on the hardware, and +the more abstract level in which procedures are protected rather than +sequences of instructions. So what does it mean to define a mutex +in terms of a serializer? But actually this could happen. Suppose +you are using a language such as Java, with high-level serialization +built in (and presumably implemented using hardware support), to write +an operating system that is supposed to provide a mutex capability to +its users. You would then write something equivalent to what this +problem asks for. What defines an abstraction is its behavior, not +how it's implemented -- this is the whole idea behind abstraction. + +The SICP version uses (LET ((CELL (LIST FALSE))) ...) because their +TEST-AND-SET! tests and modifies a pair, not a variable, mainly so that +it can be an ordinary procedure rather than a special form. In this +version there's no need to use a pair, although it wouldn't be wrong. + +The ugly (IF ((S (LAMBDA () ...))) ...) is necessary because of the way +serializers work: they take a procedure as argument and return a protected +version of that procedure, which must then actually be invoked. +We didn't take off for minor failures in the notation, accepting even +solutions in which the argument to the serializer was an expression to +be evaluated atomically: (IF (S (IF IN-USE ...)) ...) But we didn't +accept solutions in which the serializer was given data, rather than +activity, as its argument. (More on that below.) + +The reason for the nested IFs is a little subtle; the recursive call +to THE-MUTEX to retry the operation if it fails can't be inside the +serialized procedure, because then it'll block waiting for S, which is +held by this process itself -- in effect, setting up a deadlock within a +single process. But we didn't take off points for missing this subtlety. + +Some people used a single global serializer instead of a separate one +for each mutex. At first we considered this a serious error, because +it means that two mutexes can't be acquired at the same time. But then +we realized that the serializer just protects the acquiring of the mutex, +not the critical section that the mutex itself protects, so any mutex +holds the serializer only for a very short time. So we allowed a global +serializer, except in papers that also missed the point in the previous +paragraph. If a mutex can get into a deadlock with itself, while holding +a serializer needed by all the other mutexes, that's serious enough to +lose a point. + +Some solutions never actually tested whether the mutex was in use before +acquiring it. Presumably those people thought that the serializer would +protect the entire critical section, not just the acquiring, so that if +an acquire operation could get into the serializer the mutex must be free. +But that's not the case; the mutex returns to its caller once it has +set its in-use flag, so the caller's critical section is *not* keeping the +serializer busy. Such solutions got at most one point. + +There were a few common zero-point solutions. The strangest were the +ones that called parallel-execute. The job of a mutex is to protect +critical sections against other processes, not to create other processes. + +Another zero-point solution had expressions such as (S CELL) that showed +a lack of understanding of the key fact that a serializer protects +activities, not data. Similarly, no points for anything that included + + (something . args) ;; pfui + +which indicated mindless copying from the MAKE-SERIALIZER in the book +without understanding. Serializers accept as arguments procedures with +any number of arguments, but any particular use of a serializer isn't +going to be that complicated -- and none of these solutions found any +use for the ARGS variable anyway. + +Scoring: +3 OK +2 at least an atomic test-and-set implementation +1 no test-and-set, but some idea +0 way off + + +7. Streams. + +The answer we expected was + +(define all-integers + (cons-stream 0 (interleave integers + (scale-stream -1 integers)))) + +The stream generated by this expression looks like this: + + 0, 1, -1, 2, -2, 3, -3, 4, -4, ... + +You had to understand two key points to get this solution: + +1. You can't have all the integers in size order. A stream must have +a definite first element! There's no smallest negative integer. Some +people tried to REVERSE the stream of integers; that's meaningless. + +2. You can't APPEND-STREAMS two infinite streams. This is explained +in the handout you got in lecture. Since the first stream will never +finish, it's as if the second stream isn't there at all! (A few people +used MERGE, which works for two sorted, increasing streams, but not +in a case like this where one stream is growing up and one growing down.) + +There were many other correct solutions, most of which essentially +reinvented INTERLEAVE. Special mention for the following beautiful +solution (which the student unfortunately didn't get quite right): + +(define zeros-ones (cons-stream 0 (cons-stream 1 zeros-ones))) + +(define all-integers (subtract-streams zeros-ones + (cons-stream 0 all-integers))) + +where subtract-streams is like add-streams with the obvious difference. +Work this out to convince yourself that it really works! + +Scoring: + +4 correct +3 small mistakes, like leaving out zero +2 append-stream etc. +1 stream of streams, like (cons-stream negatives positives) +0 not a stream at all + +We heard from several students who thought that the stream-of-streams +solution was graded too harshly. Here's the reasoning behind this +grading policy: Most errors come from uncertainty about how to +implement an infinite stream successfully. But this error indicates +a misunderstanding about what the stream abstraction is for! Think +about the example of testing whether a number is prime. We create +a stream containing a range of numbers (range 2 14) and then we use +that as an argument to FILTER: + (filter (lambda (number) (= (remainder 15 number) 0)) + (range 2 14)) + +If RANGE returned a stream of streams, then this FILTER wouldn't +work, because the elements of the stream wouldn't be numbers! So, +even though the problem said "a stream containing all the integers" +instead of "a stream containing all the integers, in which each +element is a single integer," it's unreasonable to think that a +stream whose elements aren't numbers would be acceptable. diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/OOP/belowline.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/OOP/belowline.pdf new file mode 100644 index 0000000..5458cba --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/OOP/belowline.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/OOP/ref-man.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/OOP/ref-man.pdf new file mode 100644 index 0000000..05aec70 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/OOP/ref-man.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Therac-25.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Therac-25.pdf new file mode 100644 index 0000000..cbd6860 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Therac-25.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/mapreduce-osdi04.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/mapreduce-osdi04.pdf new file mode 100644 index 0000000..fce8825 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/mapreduce-osdi04.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/quick.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/quick.pdf new file mode 100644 index 0000000..b91e5f7 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/quick.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/r5rs.pdf b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/r5rs.pdf new file mode 100644 index 0000000..7cce72d --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/r5rs.pdf Binary files differdiff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/sicp-errata.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/sicp-errata.txt new file mode 100644 index 0000000..1467159 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/sicp-errata.txt @@ -0,0 +1,56 @@ + + + + + Errata for Structure and Interpretion of Computer Programs 2nd + edition + ________________________________________________________________ + + Positive line numbers count from the top of the page or exercise, + negative line numbers count from the bottom. + + Page 45, line -13: Exponent should be n/2, not b/2 + + Page 112, line 2 of exercise 2.30: Square-LIST should be + square-TREE. ("That is, square-tree should behave as follows:") + + Page 118, lines 1-2: Should say "...the product OF THE SQUARES + of the odd integers..." + + Page 176, before procedures rectangular? and polar?: Should say + "rectangular and polar numbers, respectively" + + Page 181, line -5: Should not refer to exercise 3.24, just to + section 3.3.3. + + Page 185, exercise 2.73a: Should ask about VARIABLE?, not + SAME-VARIABLE? + + Pages 246 and 247, figures 3.7 and 3.8: There is an extra ')' at + the end of the code. + + Page 287, figure 3.28: Rightmost box should have +, not * + + Page 324, exercise 3.50: Should refer to section 2.2.1, not + 2.2.3. + + Page 341, line 3 of exercise 3.66: Should say "For example, + APPROXIMATELY how many pairs..." + + Page 375, line 1 of exercise 4.7: Last LET should be LET* + ("...bindings of the let* variables...") + + Last updated 08/09/99 + + + + + + + + + + + + + 374 diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Volume2/word.txt b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/word.txt new file mode 100644 index 0000000..e47aa23 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Volume2/word.txt @@ -0,0 +1,121 @@ + + WORD AND SENTENCE MANIPULATION PROCEDURES + + The first chapter of the textbook deals exclusively with numeric data. + To allow some variety, with interesting examples that aren't about + calculus, we are going to use some additional Scheme procedures that + manipulate linguistic data: words and sentences. A word can be + considered as a string of characters, such as letters and digits. + (Numbers can be treated as words.) A sentence is a string of words + in parentheses. + + + PROCEDURES TO TAKE APART WORDS AND SENTENCES: + + FIRST returns the first character of a word, or + the first word of a sentence + + BUTFIRST returns all but the first character of a word, + or all but the first word of a sentence + + BF same as BUTFIRST + + LAST returns the last character of a word, or + the last word of a sentence + + BUTLAST returns all but the last character of a word, + or all but the last word of a sentence + + BL same as BUTLAST + + Examples: + + > (first 'hello) + h + + > (butlast '(symbolic data are fun)) + (symbolic data are) + + + PROCEDURES TO COMBINE WORDS AND SENTENCES + + WORD arguments must be words; returns the word with + all the arguments strung together + + SENTENCE returns the sentence with all the arguments + (words or sentences) strung together + + SE same as SENTENCE + + Examples: + + > (word 'now 'here) + nowhere + + > (se 'lisp '(is cool)) + (lisp is cool) + + + + 375 + + + + + + + + + + + PREDICATE PROCEDURES + + EQUAL? returns true if its two arguments are the same word + or the same sentence (a one-word sentence is not + equal to the word inside it) + + MEMBER? returns true if the first argument is a member of + the second; the members of a word are its letters + and the members of a sentence are its words + + EMPTY? returns true if the argument is either the empty + word [which can be represented as "" ] or the + empty sentence [which can be represented as '() ] + + + + MISCELLANEOUS + + COUNT returns the number of letters in the argument word, or + the number of words in the argument sentence. + + ITEM takes two arguments: a positive integer N, and a word or + sentence; returns the Nth letter of the word, or the Nth + word of the sentence (counting from 1). + + + + Examples: + + (define (buzz n) + (cond ((member? 7 n) 'buzz) + ((= (remainder n 7) 0) 'buzz) + (else n) )) + + (define (plural wd) + (if (equal? (last wd) 'y) + (word (bl wd) 'ies) + (word wd 's) )) + + + + + + + + + + + + + 376 |