*

4 files changed, 1469 insertions, 0 deletions

diff --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.