Lab 9:

Mutable Data, Vectors

Chapter 2 dealt with compound data as a means for constructing computational objects that have several parts, in order to model real-world objects that have several aspects. In that chapter we introduced the discipline of data abstraction, according to which data structures are specified in terms of constructors, which create data objects, and selectors, which access the parts of compound data objects. But we now know that there is another aspect of data that chapter 2 did not address. The desire to model systems composed of objects that have changing state leads us to the need to modify compound data objects, as well as to construct and select from them. In order to model compound objects with changing state, we will design data abstractions to include, in addition to selectors and constructors, operations called mutators, which modify data objects. For instance, modeling a banking system requires us to change account balances. Thus, a data structure for representing bank accounts might admit an operation

(set-balance! <account> <new-value>)

that changes the balance of the designated account to the designated new value. Data objects for which mutators are defined are known as mutable data objects. Chapter 2 introduced pairs as a general-purpose "glue" for synthesizing compound data. We begin this section by defining basic mutators for pairs, so that pairs can serve as building blocks for constructing mutable data objects. These mutators greatly enhance the representational power of pairs, enabling us to build data structures other than the sequences and trees that we worked with in section 2.2. We also present some examples of simulations in which complex systems are modeled as collections of objects with local state.

Labwork

finish this during section

Exercise 1.

Exercise 3.12 of Abelson & Sussman

Exercise 2.

Suppose that the following definitions have been provided.

(define x (cons 1 3))
(define y 2)

A CS 61A student, intending to change the value of x to a pair with car equal to 1 and cdr equal to 2, types the expression (set! (cdr x) y) instead of (set-cdr! x y) and gets an error. Explain why.

Exercise 3.

a. Provide the arguments for the two set-cdr! operations in the blanks below to produce the indicated effect on list1 and list2. Do not create any new pairs; just rearrange the pointers to the existing ones.

> (define list1 (list (list 'a) 'b))
list1
> (define list2 (list (list 'x) 'y))
list2
> (set-cdr! ________ ________)
okay
> (set-cdr! ________ ________)
okay
> list1
((a x b) b)
> list2
((x b) y)

b. After filling in the blanks in the code above and producing the specified effect on list1 and list2, draw a box-and-pointer diagram that explains the effect of evaluating the expression (set-car! (cdr list1) (cadr list2)).

Exercise 4.

Exercises 3.13 and 3.14 in Abelson & Sussman

Homework

do this in section if possible; finish the rest at home

Exercise 5.

Exercises 3.16, 3.17, 3.21, 3.25, and 3.27 in Abelson & Sussman

You don't need to draw the environment diagram for exercise 3.27; use a trace to provide the requested explanations. Treat the table procedures lookup and insert! as primitive; i.e. don't trace the procedures they call. Also, assume that those procedures work in constant time. We're interested to know about the number of times memo-fib is invoked.

Vector questions:

In all these exercises, don't use a list as an intermediate value. (That is, don't convert the vectors to lists!)

Exercise 6.

Write vector-append, which takes two vectors as arguments and returns a new vector containing the elements of both arguments, analogous to append for lists.

Exercise 7.

Write vector-filter, which takes a predicate function and a vector as arguments, and returns a new vector containing only those elements of the argument vector for which the predicate returns true. The new vector should be exactly big enough for the chosen elements. Compare the running time of your program to this version:

(define (vector-filter pred vec)
    (list->vector (filter pred (vector->list vec))))

Exercise 8.

Sorting a vector:

  1. Write bubble-sort!, which takes a vector of numbers and rearranges them to be in increasing order. (You'll modify the argument vector; don't create a new one.) It uses the following algorithm:
    1. Go through the array, looking at two adjacent elements at a time, starting with elements 0 and 1. If the earlier element is larger than the later element, swap them. Then look at the next overlapping pair (0 and 1, then 1 and 2, etc.).
    2. Recursively bubble-sort all but the last element (which is now the largest element).
    3. Stop when you have only one element to sort.
  2. Prove that this algorithm really does sort the vector. Hint: Prove the parenthetical claim in step 2.
  3. What is the order of growth of the running time of this algorithm?

Exercise 9.

Do the following reading:

Project 3

Finish this before the deadline. Apart from that, we don't care when.

You should be starting part 2 of the project this week.

Extra for Experts

Do this if you want to. This is NOT for credit.

Exercise 10.

Abelson & Sussman, exercises 3.19 and 3.23.

Exercise 3.19 is incredibly hard but if you get it, you'll feel great about yourself. You'll need to look at some of the other exercises you skipped in this section. Exercise 3.23 isn't quite so hard, but be careful about the O(1) - i.e. constant-time requirement.

Exercise 11.

Write the procedure cxr-name. Its argument will be a function made by composing cars and cdrs. It should return the appropriate name for that function:

> (cxr-name (lambda (x) (cadr (cddar (cadar x)))))
CADDDAADAR