-
Notifications
You must be signed in to change notification settings - Fork 14
/
mt1-1_solutions.txt
423 lines (314 loc) · 13.4 KB
/
mt1-1_solutions.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
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