# Exercise 1.

Exercise 3.12 of Abelson & Sussman

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.

Exercise 3.12 of Abelson & Sussman

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.

**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))`.

Exercises 3.13 and 3.14 in Abelson & Sussman

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.

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

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.

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))))
```

Sorting a vector:

- 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:- 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.).
- Recursively bubble-sort all but the last element (which is now the largest element).
- Stop when you have only one element to sort.

- Prove that this algorithm really does sort the vector. Hint: Prove the parenthetical claim in step 2.
- What is the order of growth of the running time of this algorithm?

Do the following reading:

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

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.

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

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