*

3 files changed, 423 insertions, 0 deletions

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 differ