*

1 files changed, 459 insertions, 0 deletions

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.