# set-2

## Exercise 2.92

By imposing an ordering on variables, extend the polynomial package so that addition and multiplication of polynomials works for polynomials in different variables. (This is not easy!)

## Exercise 2.76

As a large system with generic operations evolves, new types of data objects or new operations may be needed. For each of the three strategies — generic operations with explicit dispatch, data-directed style, and message-passing-style — describe the changes that must be made to a system in order to add new types or new operations. Which organization would be most appropriate for a system in which new types must often be added? Which would be most appropriate for a system in which new operations must often be added?

## Exercise 2.75

Implement the constructor `make-from-mag-ang`

in message-passing style. This procedure should be analogous to the `make-from-real-imag`

procedure given above.

## Exercise 2.65

## Exercise 2.64

The following procedure `list->tree`

converts an ordered list to a balanced binary tree. The helper procedure `partial-tree`

takes as arguments an integer `n` and list of at least `n` elements and constructs a balanced tree containing the first `n` elements of the
list. The result returned by `partial-tree`

is a pair (formed
with `cons`

) whose `car`

is the constructed tree and whose `cdr`

is the list of elements not included in the tree.

```
define (list->tree elements)
(car (partial-tree elements (length elements))))
(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))
```

Write a short paragraph explaining as clearly as you can how

`partial-tree`

works. Draw the tree produced by`list->tree`

for the list`(1 3 5 7 9 11)`

.What is the order of growth in the number of steps required by

`list->tree`

to convert a list of`n`elements?

## Exercise 2.63

Each of the following two procedures converts a binary tree to a list.

```
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))
```

Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with

`n`elements to a list? If not, which one grows more slowly?

## Exercise 2.45

`Right-split`

and `up-split`

can be expressed as instances of a general splitting operation. Define a procedure `split`

with the property that evaluating

```
(define right-split (split beside below))
(define up-split (split below beside))
```

produces procedures `right-split`

and `up-split`

with the same behaviors as the ones already defined.

## Exercise 2.43

Louis Reasoner is having a terrible time doing exercise 2.42. His `queens`

procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6 × 6 case.) When Louis asks Eva Lu Ator for help, she points
out that he has interchanged the order of the nested mappings in the `flatmap`

, writing it as

```
(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
(adjoin-position new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))
```

Explain why this interchange makes the program run slowly. Estimate
how long it will take Louis’s program to solve the eight-queens
puzzle, assuming that the program in exercise 2.42 solves the puzzle in time `T`.

## Exercise 2.42

The “eight-queens puzzle” asks how to place eight queens on a
chessboard so that no queen is in check from any other (i.e., no two
queens are in the same row, column, or diagonal). One possible
solution is shown in figure 2.8. One way to solve the
puzzle is to work across the board, placing a queen in each column.
Once we have placed `k` - 1 queens, we must place the `k`th queen in a position where it does not check any of the queens already on the
board. We can formulate this approach recursively: Assume that we
have already generated the sequence of all possible ways to place
`k` - 1 queens in the first `k` - 1 columns of the board. For each of
these ways, generate an extended set of positions by placing a queen
in each row of the `k`th column. Now filter these, keeping only
the positions for which the queen in the `k`th column is safe with
respect to the other queens. This produces the sequence of all ways
to place `k` queens in the first `k` columns. By continuing this
process, we will produce not only one solution, but all solutions to
the puzzle.

We implement this solution as a procedure `queens`

, which returns
a sequence of all solutions to the problem of placing `n` queens on an
`n`× `n` chessboard. `Queens`

has an internal procedure `queen-cols`

that returns the sequence of all ways to place queens in the first `k` columns of the board.

```
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
```

In this procedure `rest-of-queens`

is a way to place `k` - 1 queens in the first `k` - 1 columns, and `new-row`

is a proposed row in which to place the queen for the `k`th column. Complete the program by implementing the representation for sets of board positions, including the procedure `adjoin-position`

, which adjoins a new row-column position to a set of positions, and `empty-board`

, which represents an empty set of positions. You must also write the procedure `safe?`

, which determines for a set of positions, whether the queen in the `k`th column is safe with respect to the others. (Note that we need only check whether the new queen is
safe — the other queens are already guaranteed safe with respect to
each other.)

## Exercise 2.41

Write a procedure to find all ordered triples of distinct positive integers `i`, `j`, and `k` less than or equal to a given integer `n` that sum to a given integer `s`.