DOC PREVIEW
Berkeley COMPSCI 61A - Homework

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

How to Start and SubmitMutable DataVectorsMeta-Circular EvaluatorExtra for Experts (Optional)FeedbackCS61A: Structure and Interpretation of Computer Programs Homework 5CS61A Summer 2010George Wang, Jonathan Kotker, Seshadri Mahalingam, Steven Tang, Eric TzengHomework 5Due: Monday, July 26 2010, at 7AMN ote: The number of stars (F) besides a question represents the estimated relative difficulty of the problem:the more the number of stars, the harder the question.1 How to Start and SubmitFirst, download http://inst.eecs.berkeley.edu/~cs61a/su10/hw/hw5.scm and use it as a templatewhile filling out your procedures. See http://www-inst.eecs.berkeley.edu/~cs61a/su10/hw-faq.pdffor submission instructions.2 Mutable Data1. (FF) Draw a box and pointer diagram for the following sequence of expressions.> (define a (list 1 2 3))> (define b (list 1 2 3))> (define c (cons a b))> (define d (list c (cdr a) (cadr b)))> (define e (list 0 1 2))> (set-cdr! (cdr e) (cdadr d))2. (F) Write the procedure append! that, given two lists, appends the second list onto the first usingONLY list mutation: do not create any new pairs.Examples:> (define a (list 1 2 3))> (define b (list 4 5 6))> (append! a b)> a(1 2 3 4 5 6)> b(4 5 6)3. (FF) Write the procedure merge! that, given two lists (both are lists of numbers only and both arein increasing order) combines the list such that the resulting list is in increasing numerical order aswell. Use ONLY list mutation, d o not create any new pairs.Examples:> (merge! (list 2 3 5 9) (list 1 6 7 11))(1 2 3 5 6 7 9 11)4. (FF) SICP Exercises: count-pairs(a) 3.16(b) 3.17Page 1CS61A: Structure and Interpretation of Computer Programs Homework 55. (FF) Queue Implementation: SICP Exercise 3.21.We strongly recommend reading the section on queues in SICP before attempting the question.6. (FFF) (Optional) Memoization: SICP Exercise 3.273 VectorsN ote: For the following questions, please do not use list->vector, vector->list or apply. Use vectorprocedures like make-vector and vector-set!.1. (F) Write a procedure called vsearch that searches an unsorted vector for a given element and returnsthe location index of that item (remember that vectors, like lists, are numbered starting at 0). If theelement is not found in the vector, return -1. In general, does this seem like this would take more time,less time, or the same amount of time doing such a search on a list?Examples:> (define sample-vec (make-vector 5 12)#(12 12 12 12 12)> (vector-set! sample-vec 3 6)okay> sample-vec#(12 12 12 6 12)> (vsearch sample-vec 6)3> (vsearch ’q (vector ’h ’i ’j ’k ’l))-12. (FF) Write a procedure called vector-append for vectors that appends two vectors, like the ’append’procedure does for lists.Examples:> (vector-append (make-vector 3 ’a) (make-vector 2 ’q))#(a a a q q)> (vector-append (vector ’a ’b ’c) (vector 1 2 3))#(a b c 1 2 3)3. (F) Write a procedure vector-reverse that takes a vector and returns a new vector with the entriesof the given vector reversed.Examples:> (vector-reverse (vector ’a ’b ’c))#(c b a)> (vector-reverse (vector 1))#(1)4. (FFF) Write a procedure vector-filter that takes a predicate function and a vector as argumentsand returns a new vector containing only those elements of the argument vector for which the predicatewas true. The new vector must exactly big enough for these elements that are true in the predicate.How does the runtime of your procedure compare with this:(define (vector-filter pred vec)(list->vector (filter pred (vector->list vec))))5. (FF) Remember vector-reverse? Great! Write the procedure vector-reverse! that reverses agiven vector “in place”. In other words, do not create a new vector; use the given one only.Page 2CS61A: Structure and Interpretation of Computer Programs Homework 5Examples:> (define sample-vec (vector 1 2 3 4 5))> (vector-reverse! sample-vec)#(5 4 3 2 1)> sample-vec#(5 4 3 2 1)4 Meta-Circular Evaluator1. The following SICP exercises are designed to familiarize yourself with the structure of the metacircularevaluator by incrementally adding features. We recommend that you do the following exercises in thegiven order. Some are less directed and more open-ended than others and require you to make and/orjustify design decisions.• (F) 4.2(a) : cond clauses• (FF) 4.4 : and & or• (FF) 4.5 : (<test> => <recipient>) cond clauses• (FF) 4.6 : let• (FF) (Optional) 4.7 : let*• (F) 4.13 : make-unbound!• (FFF) 4.14 : Why doesn’t primitive map work?2. (FFF) (Optional) Modify the metacircular evaluator to allow type-checking of arguments to proce-dures. Here’s how the feature should work:When a new procedure is defined, a formal parameter can be either a symbol (as usual) or a list oftwo elements. In the second case: The first value will be a predicate procedure of one argument thatreturns #t if the argument is of the desired type. The second value will be the name of the formalparameter.Example:MCE> (define (foo (integer? num) ((lambda (x) (not (null? x))) list))(list-ref list num))fooMCE> (foo 3 ’(a b c d e))dMCE> (foo 3.5 ’(a b c d e))Error: wrong argument type -- 3.5MCE> (foo 2 ’())Error: wrong argument type -- ()5 Extra for Experts (Optional)SICP Exercises 4.16 - 4.21. These exercises explore the subtle differences in how variables are defined andscoped, using recursion, mutual recursion and environment diagrams.Page 3CS61A: Structure and Interpretation of Computer Programs Homework 56 FeedbackNow that you are done, please leave me some feedback at the following link regarding how the course is go-ing. This is not worth points, but will give us valuable feedback that in turn improves your course experience.Thanks! https://spreadsheets.google.com/viewform?formkey=dDlZX1I2OGc1dk5GOEN3Y0VqZi1zUnc6MQPage


View Full Document

Berkeley COMPSCI 61A - Homework

Documents in this Course
Lecture 1

Lecture 1

68 pages

Midterm

Midterm

5 pages

Midterm

Midterm

6 pages

Lecture 35

Lecture 35

250 pages

Lecture 14

Lecture 14

125 pages

Lecture 2

Lecture 2

159 pages

Lecture 6

Lecture 6

113 pages

Lecture 3

Lecture 3

162 pages

Homework

Homework

25 pages

Lecture 13

Lecture 13

117 pages

Lecture 29

Lecture 29

104 pages

Lecture 11

Lecture 11

173 pages

Lecture 7

Lecture 7

104 pages

Midterm

Midterm

6 pages

Midterm

Midterm

6 pages

Lecture 8

Lecture 8

108 pages

Lab 4

Lab 4

4 pages

Lecture 7

Lecture 7

52 pages

Lecture 20

Lecture 20

129 pages

Lecture 15

Lecture 15

132 pages

Lecture 9

Lecture 9

95 pages

Lecture 30

Lecture 30

108 pages

Lecture 17

Lecture 17

106 pages

Load more
Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?