DOC PREVIEW
Berkeley COMPSCI 61A - CS 61A Sample Final

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Sample final exam #1Problem 1 (Higher order procedures).Write a procedure ordinal that takes a nonnegative integer argument n. It should returna procedure that takes a list as argument and returns the nth element of the list (countingfrom one):> (define third (ordinal 3))> (third ’(John Paul George Ringo))GeorgeHint: list-refProblem 2 (Iterative and recursive processes).The following recursive procedure takes a list of integers and returns the number of el ementsthat are even.(define (count-evens ints)(cond ((null? ints) 0)((even? (car ints)) (+ 1 (count-evens (cdr ints))))(else (count-evens (cdr ints)))))Rewrite this as an iterative procedure by filling i n the blanks below.(define (count-evens ints)(define (helper)(cond))(helper))205Problem 3 (Abstract data types).The following program is designed for use with the “world tree” discussed in lecture, inwhich the nodes represent geographical regions (contries, states, cities). The selectors forTrees are datum and children. The datum at each node is a word or sentence. Theprogram, which returns a list of al l the cities whose first word i s “San,” does not respectdata abstraction:(define (find-san-cities tree)(if (null? (cdr tree)) ; Is this node a city?(if (equal? (car (car tree)) ’San)(list (car tree))’())(san-helper (cdr tree))))(define (san-helper forest)(if (null? forest)’()(append (find-san-cities (car forest))(san-helper (cdr forest)))))In t he version below, each car and cdr has been replaced by a blank. Fill in the blankswith the correct selectors, respecting all t he relevant abstract data types:(define (find-san-cities tree)(if (null? (tree))(if (equal? (( tree)) ’San)(list (tree))’())(san-helper (tree))))(define (san-helper forest)(if (null? forest)’()(append (find-san-cities (forest))(san-helper (forest)))))206Problem 4 (Trees).Consider the fol lowing program:(define (cost tree)(cost-help tree 0))(define (cost-help tree above)(let ((new (+ (datum tree) above)))(make-node new(map (lambda (child) (cost-help child new))(children tree)))))If cost is called with the following Tree as its argument, draw the Tree that it returns.3/ \/ \2 1/ \ / \1 0 5 3Problem 5 (Generic operators).There’s a collection of programs called netpbm that is used to convert imag es from oneformat to another (for example, to convert gif files to jpeg files). The coll ection consists ofaround 160 converters. Each converter is a program that knows how to convert a file in onespecific format to one other format. So, for example, there’s a converter called tifftopnmthat converts i ma ges in t iff format to images in pnm format.The documentation for netpbm claims that the programs can be used to convert to andfrom any of 80 image formats. How is this possible with only 160 converters?Your answer must be no more than 30 words!207Problem 6 (Object oriented programming).Here is a definition in OOP language of the class line-obj from project 4:(define-class (line-obj text)(method (next)(let ((result (car text)))(set! text (cdr text))result))(method (empty?) (null? text))(method (put-back token) (set! text (cons token text))) )Write an equivalent program in ordinary Scheme without using the OOP language. Hereis an ex ample of how your program will be used:> (define logo-line (make-line-obj ’(print 3 print 4 print 5)))okay> (logo-line ’next)print> (logo-line ’next)3> (logo-line ’empty?)#f> ((logo-line ’put-back) ’hello) ;note double parenthesesokay> (logo-line ’next)hello> (logo-line ’next)printDon’t check for errors. Here is the first line of the program, continue from here:(define (make-line-obj text)208Problem 7 (Environment diagrams).Consider the fol lowing definitions.(define x 1)(define (charm x)(lambda (y) (+ x y)))(define z ((charm 3) 5))Below are two partial environment dia grams for these definitions. They are missing twothings:(1) An arrow from the y --> 5 frame to the environment that it extends;(2) The value of z in the global frame.Complete the first diagram as it would appear in lexically scoped Scheme; complete thesecond diagram as it would appear if Scheme used dynamic scope.LEXICAL SCOPE DYNAMIC SCOPE------------- -------------____global_ ____global_| | | || x --> 1 |<------------, | x --> 1 |<------------,| | _ | | | _ || charm ------------>(_)(_) | charm ------------>(_)(_)| | params: x | | params: x| z -->___ | body: (lambda (y) | z -->___ | body: (lambda (y)| | (+ x y)) | | (+ x y))| |<------------, | |<------------,|___________| | |___________| |___|_______ ___|_______| | | |+--------->| x --> 3 | +--------->| x --> 3 || |___________| | |___________|(_)(_) (_)(_)params: y params: ybody: (+ x y) ___________ body: (+ x y) ___________| | | || y --> 5 | | y --> 5 ||___________| |___________|209Problem 8 (Mutation).Write the procedure interleave! t hat t akes two lists (not streams!) as arguments a ndreturns the result of interleaving them. It must do its job by mut ation, withoutallocating any new pairs! Example:> (define x (list ’a ’b ’c ’d ’e))> (define y (list 1 2 3 4 5 6 7 8))> (define z (interleave! x y))> z(a 1 b 2 c 3 d 4 e 5 6 7 8)> x(a 1 b 2 c 3 d 4 e 5 6 7 8)> y(1 b 2 c 3 d 4 e 5 6 7 8)Note that either list might be shorter than the other; your procedure should handle thissituation correctly.Our solution uses five lines of code; if yours takes more than ten, you’re probably notthinking about this properly.210Problem 9 (Concurrency).Consider the fol lowing t hree procedures and two serializers.(define (incr) (set! x (+ x 1)))(define (decr) (set! x (- x 1)))(define (double) (set! x (* x 2)))(define s (make-serializer))(define t (make-serializer))In each of t he following situat ions, what outcomes are possible? For each case, choose thesingle best answer.(define x 0)(parallel-execute (s (t incr)) (s (t decr)) double)x is -1, 0, or 1x is -1, 0, or 1 , o r possible deadlockx is -2, -1, 0, 1, or 2x is -2, -1, 0, 1, or 2, or possible deadlock(define x 0)(parallel-execute (s incr) (s (t decr)) (s double))x is -1, 0, or 1x is -1, 0, or 1 , o r possible deadlockx is -2, -1, 0, 1, or 2x is -2, -1, 0, 1, or 2, or possible deadlock211Problem 10 (MapReduce).Suppose we’ve done some MapReduce computations, and now we have my-pairs, thefollowing stream of key-value pairs:> (ss my-pairs)((bar . 2) (bat . 3) (baz . 1) (big . 8) (bill . 7) (bin . 6) (bog . 0))Now, what is the stream returned by each of the following call s to mapreduce? If theresult is an error, just say ERROR. Otherwise,


View Full Document

Berkeley COMPSCI 61A - CS 61A Sample Final

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 CS 61A Sample Final
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 CS 61A Sample Final 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 CS 61A Sample Final 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?