This preview shows page 1-2 out of 6 pages.

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

Unformatted text preview:

Sample midterm 1 #3Problem 1 (What will Scheme print?).What will Scheme print in response to the following expressions? If an expression producesan error message, you may just say “error”; you don’t have to provide the exact text ofthe message. If the value of an expression is a procedure, just say “procedure”; you don’thave to show the form in which Scheme prints procedures.(first ’(help!))((word ’but ’first) ’plop)(let ((+ -)(- +))(- 8 2))What will Scheme print in response to the following expressions? If an expression producesan error message, you may just writ e “error”; you don’t have to provide the exact text ofthe message. Also, draw a box and pointer diagramfor the value produced byeach expression.(list (append ’(a b) ’()) (cons ’(a b) ’(c)))(filter (lambda (x) (if (list? x) (pair? x) (number? x)))’(1 () (2 3) (so) what))(cddadr ’((a b c d e) (f g h i j) (l m n o p) (q r s t u)))Problem 2 (Orders of growth).Suppose that you have a procedure (f n) that requires time Θ(n), and a procedure (g n)that requires time Θ(n2). What is the order of growth required for a program to compute(* (f n) (g n))? There may be more than one correct answer; check all thatare correct.A. Θ(n) B. Θ(n2)C. Θ(n + n2) D. Θ(n3)141Problem 3 (Iterative/recursive processes).Consider the function defined as follows:lg(1) = 0lg(n) = lg(⌊n/2⌋) + 1, n > 1In this problem you will write two Scheme procedures to compute this function. Use thealgorithm shown above; do notuse mathematical functions not shown here, such asexpt or sqrt. You may use (floor x) to compute ⌊x⌋.(a) Wri te a procedure that computes this function using a recursiveprocess.(b) Write a procedure that computes this function using an iterativeprocess.Problem 4 (Normal/applicative order).Given the primitive procedure random discussed in lecture, and the procedure squaredefined as follows:(define (square x)(* x x))Which of the following expresions may have a different value depending on whether applica-tive order or normal order is used? There may be more than one correct answer;check all that are correct.A. (random 10)B. (* (random 10) (random 10))C. (square (random 10))D. (random (square 10))142Problem 5 (Recursive procedures).Mad LibsTMis a campfire game in which players fill in blank places in a story, therebycreating a hilarious new story. We wish to implement this in Scheme.Mad-libs is a procedure that takes a sentence story as its argument. Some o f the wordsin story begin with ‘*’, meaning they are to be replaced. Mad-libs returns a procedurethat takes two sentences , nouns and adjectives, a nd replaces, in order, words from storybeginning with ‘*’ with words from nouns if the word is *NOUN or from adjectives if theword is *ADJECTIVE. For example, an infamous author once wrote:It was a dark and stormy night... and the rai n fell in torrents – except at occasionalintervals, when it was checked by a violent gust of wind which swept up the streets ( for itis in London that our scene lies), rattling along the housetops, and fiercely agitating thesca nty flame of the lamps that struggled against the darkness. —Paul Clifford (1830)(define my-story(mad-libs ’(It was a *ADJECTIVE and *ADJECTIVE *NOUN)))> (my-story ’(night) ’(dark stormy))(It was a dark and stormy night)> (my-story ’(midterm) ’(fun easy))(It was a fun and easy midterm)Write mad-libs. You may assume that the lengths of nouns and of adjectives are exactlythe same as the number of words of that category in story.143Problem 6 (Higher order procedures).We are going to generalize the idea of(define (plural wd)(word wd ’s))by allowing any prefix and/or suffix to be added to a word. Here are some examples:> (define plural (word-maker ’(* s)))> (plural ’book)books> (define past (word-maker ’(* ed)))> (past ’walk)walked> ((word-maker ’(re *)) ’write)rewrite> ((word-maker ’(de * ing)) ’construct)deconstructing> ((word-maker ’(* -vs- *)) ’spy)spy-vs-spyWord-maker takes a sentence, called a template, as its argument. It returns a function thattakes a word as argument and returns another word based on the template, but with any* in the templat e replaced with the argument word, a nd the result scrunched into a word.Write word-maker.Don’t use recursion; use higher-order functions. Here’s a helper function for you:(define (scrunch sent)(if (empty? sent)""(word (first sent) (scrunch (butfirst sent)))))> (scrunch ’(here there and everywhere))herethereandeverywhere144Problem 7 (Data abstraction).An association list is a list of pairs, each of which associates a name (the key) with a value.For example, the association list((a . 3) (b . 7) (c . foo))associates the key A with the value 3, the key B with the value 7, and the key C with thevalue FOO.Here are a constructor and two selectors for an assoc iation abstract data type:(define make-association cons)(define association-key car)(define association-value cdr)Note that this is an ADT for an association, not for an association list, whichis just a sequence of associations.(a) Scheme provides the procedure assoc for looking up a key in an association list. Itreturns the entire association, not just the value. Here is an implementation of assoc:(define (assoc key a-list)(cond ((null? a-list) #f)((equal? key (caar a-list)) (car a-list))(else (assoc key (cdr a-list)))))(Both caar and car in the next-to-last line above are correct!)Rewrite assoc to use the association ADT defined above. Don’t make any unnecessarychanges; your program should l ook much like the one above, but with some procedure callsrenamed.(Problem continues on the next page.)145(b) We are given an association list in which the keys are names of musical groups and thevalues a re sentences of names of the g ro up members, like this:((Beatles . (John Paul George Ringo))((Buffalo Springfield) . (Steve Neil Ritchie Dewey Bruce))(Who . (Pete Alec Roger Keith))What follows is a procedure to make a “backwards” associati o n list in which the keys arethe musicians and the values are t heir groups, like t his example:((John . Beatles) (Paul . Beatles) (George . Beatles) (Ringo . Beatles)(Steve . (Buffalo Springfield)) (Neil . (Buffalo Springfield))(Richie . (Buffalo Springfield)) (Dewey . (Buffalo Springfield))(Bruce . (Buffalo Springfield)) (Pete . Who) (Alec . Who)(Roger . Who) (Keith . Who))(Note to ’60s rock fans: I’ve listed John Alec Entwistle by his middle name so that


View Full Document

Berkeley COMPSCI 61A - Midterm

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

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 Midterm
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 Midterm 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 Midterm 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?