DOC PREVIEW
Berkeley COMPSCI 61A - CS61A DISCUSSION NOTES

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

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

Unformatted text preview:

CS61A DISCUSSION NOTES 4.5WHAT DOES SCHEME PRINT?Write down what Scheme will show if you type these expressions into the interpreter.1. (let ((x 3)) (lambda (y) (+ x y)))2. ((lambda (x) (let ((+ -)) x)) (+ 3 2))3. (and or (not #f) (not not) 2)4. ((word ‘but ‘first) ‘hello)BOXES AND POINTERSWrite down what the list looks like and draw the box and pointer diagrams.1. (cons (list 1 3) (append (list (cons 2 3)) (list 4)))2. (list (append (list 3) (cons 4 ’())))3. (cons (list 2 4) (list 3 6))4. (cons (cons 3 1) (list))5. (define x ‘(1 (2 3)))a. draw x.b. what does (cdr x) return?Lovingly crafted by Kevin Hwang, Phillip Carpenter, Stephanie Rogers, Eric Tzeng, and Hamilton Nguyen for Summer 2011ORDERS OF GROWTH1. Suppose a procedure foo requires time ( n) and a procedure bar requires time ( logn). Also, foo returns n and bar returns log n. What time do the following procedurecalls require?a. (* (foo n) (foo n))b. (foo (bar n))c. (bar (foo n))2a. Write a procedure (fib n) to calculate the nth Fibonacci number. Use a recursiveprocess. What is the order of growth? The nth Fibonacci number is given by F(n) = F(n-2) + F(n-1).b. Now rewrite fib using an iterative process. What is the order of growth? Is thisbetter or worse than the version in part a?3. What does the following code produce in applicative order? Normal order?a. (define (iwontstop n) (iwontstop (- n 1)))b. (define (makemenormal x y) (if (> y 0) y x))c. (makemenormal (iwontstop 3) 5Lovingly crafted by Kevin Hwang, Phillip Carpenter, Stephanie Rogers, Eric Tzeng, and Hamilton Nguyen for Summer 2011LISTS1. This exercise will have you implement mergesort, a sorting algorithm.a. Given two lists of numbers, write a procedure called merge that returns a list in which the two lists of numbers are “merged” into increasing order. So, for example, (merge (list 1 3 4 6) (list 3 5 7 8)) returns the list (1 3 4 5 6 7 8), while (merge (list 1 2 3 4) (list 5 6 7 8)) returns (list 1 2 3 4 5 6 7 8). You should assume that the lists are already in increasing order.b. Given a list of numbers, write a procedure called sublist that also takes in two arguments – start and end – and returns the sublist that starts at position start and ends at position end. Assume that the list indices start from 0. For example, (sublist (list 2 3 4 5) 1 3) should return the list (3 4 5).c. We will now implement the mergesort algorithm to sort a list of numbers into increasing order. The algorithm works as follows:i. If a list is of length zero or one, then the list is already sorted.ii. Otherwise, we separate the list into two smaller, equally-sized lists, sort the smaller lists, and merge the two sorted lists.Implement the procedure called mergesort that takes in a list of numbers and sorts the list using the mergesort algorithm.DATA ABSTRACTIONLet’s implement a very simple representation of Pokemon. A Pokemon’s attributes will simply contain three e lds, de ned in the following way:(define (pokemon type level experience) (list type level experience))We wish to be able to reference a Pokemon’s attributes, but we want to do so in a meaningful way.Lovingly crafted by Kevin Hwang, Phillip Carpenter, Stephanie Rogers, Eric Tzeng, and Hamilton Nguyen for Summer 2011a. Write the selectors for type, level, and experience. For example, aPokemon’s type would be de ned thus: (define type car).b. Now we wish to be able to make our Pokemon battle each other:First, if one Pokemon is at least five levels above the other, it automatically wins. Next, if the Pokemon are within five levels of each other, the super-effective type wins. Finally, if neither of the above is true, whoever has more experience wins. The procedure pokemon-battle should return the winner, given two Pokemon poke1and poke2. You may assume that the procedure super-effective is written. It takes two types and returns true if the r st is super-e ective against the second. Remember to respect the abstraction!c. Now suppose that for some weird reason, we decided to change the representation ofPokemon attributes to the following:(define (pokemon type level experience) (list (cons level experience) type))Rewrite the selectors so that pokemon-battle still works as intended.Lovingly crafted by Kevin Hwang, Phillip Carpenter, Stephanie Rogers, Eric Tzeng, and Hamilton Nguyen for Summer 2011HIGHER ORDER FUNCTIONS1. Write sentfn, a procedure that takes an arithmetic function and a list ofsentences of numbers and returns a new list of sentences that is theresult of calling the function on each number in each sentence. For example:> (sentfn square ‘((2 5) (3 1 6)))((4 25) (9 1 36))Use higher order functions, not recursion, and respect the abstraction!2. sum is a procedure that takes as an argument a sentence and returns the sum of all the numbers in that sentence and the letter count of the words in the sentence.ex: (sum ‘(i can do it 9 times)) = 22(sum '(20 percent cooler)) = 33a. Write sum using recursion. Do not use higher order functions.b. Write sum using higher order functions. Do not use recursion.Lovingly crafted by Kevin Hwang, Phillip Carpenter, Stephanie Rogers, Eric Tzeng, and Hamilton Nguyen for Summer


View Full Document

Berkeley COMPSCI 61A - CS61A DISCUSSION NOTES

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 CS61A DISCUSSION NOTES
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 CS61A DISCUSSION NOTES 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 CS61A DISCUSSION NOTES 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?