DOC PREVIEW
Berkeley COMPSCI 61A - CS61A Notes – Fake Plastic Trees

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

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

Unformatted text preview:

CS61A Notes 02b – Fake Plastic TreesBox and Pointer DiagramsQUESTIONS: Evaluate the following, and draw a box-and-pointer diagram for each. (Hint: It may beeasier to draw the box-and-pointer diagram first.)1. (cons (cons 1 2) (cons 3 4))2. (cons ‘((1 a) (2 o)) ‘(3 g))3. (list ‘((1 a) (2 o)) ‘(3 g))4. (append ‘((1 a) (2 o)) ‘(3 g))5. (cdr (car (cdr ‘(((1) 3) (4 (5 6))) )))6. (map (lambda (fn) (cons fn (fn 6))) (list square 1+ even?))(Slightly) Harder Lists1. Define a procedure (depth ls) that calculates the maximum depth of sublists in ls. Forexample,(depth ‘(1 2 3 4)) => 1(depth ‘(1 2 (3 4) 5)) => 2(depth ‘(1 2 (3 4 5 (6 7) 8) 9 (10 11) 12)) => 3Remember that there’s a procedure called max that takes in two numbers and returns thegreater of the two.2. Define a procedure (remove item ls) that takes in a list and returns a new list withitem removed from ls.3. Define a procedure (unique-elements ls) that takes in a list and returns a new listwithout duplicates. You’ve already done this with remove-dups, and it used to do this:(remove-dups ‘(3 5 6 3 3 5 9 8)) ==> (6 3 5 9 8)where the last occurrence of an element is kept. We’d like to keep the first occurrences:(unique-elements ‘(3 5 6 3 3 5 9 8)) => (3 5 6 9 8)Try doing it without using member?. You might want to use remove above.4. Define a procedure (count-of item ls) that returns how many times a given itemoccurs in a given list; it could also be in a sublist. So,(count-of ‘a ‘(a b c a a (b d a c (a e) a) b (a))) => 75. Define a procedure (count-unique ls) which, given a list of elements, returns a list ofpairs whose car is an element and whose cdr is its number of occurrences in the list. Forexample,(count-unique ‘(a b b b c d d a e e f a a))=> ((a . 4) (b . 3) (c . 1) (d . 2) (e . 2) (f . 1))You might want to use unique-elements and count-of defined above.6. Define a procedure (interleave ls1 ls2) that takes in two lists and returns one listwith elements from both lists interleaved. So,(interleave ‘(a b c d) (1 2 3 4 5 6 7)) => (a 1 b 2 c 3 d 4 5 6 7)7. Write a procedure (apply-procs procs args) that takes in a list of single-argumentprocedures and a list of arguments. It then applies each procedure in procs to eachelement in args in order. It returns a list of results. For example,(apply-procs (list square double +1) ‘(1 2 3 4))=> (3 9 19 33)Fake Plastic TreesA tree is, abstractly, an acyclic, connected set of nodes (of course, that’s not a very friendly definition).Usually, it is a node that contains two kinds of things – data and children. Data is whateverinformation may be associated with a tree, and children is a set of subtrees with a node as the parent.Concretely, it is often just a list of lists of lists of lists in Scheme, but it’s best NOT to think of trees aslists at all. Trees are trees, lists are lists. They are completely different things, and if you, say, call(car tree) or something like that, that violates the data abstraction. car, cdr, list andappend are for lists, not trees! And don’t bother with box-and-pointer diagrams – they get way toocomplicated for trees. Just let the data abstraction hide the details from you, and trust that theprocedures like make-tree work as intended.Of course, that means we need our own procedures for working with trees analogous to car, cdr,etc. Different representations of trees use different procedures. You have already seen the ones fora general tree, which is one that can have any number of children (not just two) in any order (notgrouped into smaller-than and larger-than). Its operators are:;; takes in a datum and a LIST of trees that will be the children of this;; tree, and returns a tree.(define (make-tree label children) ...);; returns the datum at this node.(define (datum tree) ...);; returns a LIST of trees that are the children of this tree.;; NOTE: we call a list of trees a FOREST(define (children tree) ...)With general trees, you’ll often be working with mutual recursion. This is a common structure:(define (foo-tree tree)...(foo-forest (children tree)))(define (foo-forest forest)...(foo-tree (car forest))...(foo-forest (cdr forest)))Note that foo-tree calls foo-forest, and foo-forest calls foo-tree! Mutual recursion isabsolutely mind-boggling if you think about it too hard. The key thing to do here is – of course –TRUST THE RECURSION! If when you’re writing foo-tree, you BELIEVE that foo-forest isalready written, then foo-tree should be easy to write. Same thing applies the other way around.QUESTIONS1. Write (square-tree tree), which returns the same tree structure, but with every elementsquared. Don’t use “map”!2. Write (max-of-tree tree) that does the obvious thing. The tree has at least one element.3. Write (listify-tree tree) that turns the tree into a list in any order. (This one you can’t usemap even if you tried... Muwahahaha.)Binary Search TreesA binary search tree is a special kind of tree with an interesting restriction – each node only has twochildren (called the “left subtree” and the “right subtree”, and every node in the left subtree has datumsmaller than the node of the root, and every node in the right subtree has datum larger than the nodeof the root. Here are some operators:;; takes a datum, a left subtree and a right subtree and make a bst(define (make-tree datum left-branch right-branch) ...);; returns the datum at this node(define (datum bst) ...);; returns the left-subtree of this bst(define (left-subtree bst) ...);; returns the right-subtree of this bst(define (right-subtree bst) ...)So then, let’s get to it!QUESTIONS1. Jimmy the Smartass was told to write (valid-bst? bst) that checks whether a tree satisfiesthe binary-search-tree property – elements in left subtree are smaller than datum, and elements inright subtree are larger than datum. He came up with this:(define (valid-bst? bst)(cond ((null? bst) #t)(else (and (or (null? (left-branch bst))(and (< (datum (left-branch bst)) (datum bst))(valid-bst? (left-branch bst))))(or (null? (right-branch bst))(and (> (datum (right-branch bst)) (datumbst))(valid-bst? (right-branch bst))))))))Why will Jimmy never succeed in life? Give an example that would fool his pitiful procedure.2. Write (sum-of bst) that takes in a binary search tree, and returns the sum of all the data inthe tree.3. Write (max-of bst) that takes in a binary search tree, and returns the maximum datum in thetree. The tree has at least one element.4.


View Full Document

Berkeley COMPSCI 61A - CS61A Notes – Fake Plastic Trees

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 Notes – Fake Plastic Trees
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 Notes – Fake Plastic Trees 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 Notes – Fake Plastic Trees 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?