Problem 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 \times 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\).
Problem 46
A two-dimensional vector \(\mathbf{v}\) running from the origin to a point can be represented as a pair consisting of an \(x\)-coordinate and a \(y\)-coordinate. Implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of your selectors and constructor, implement procedures add-vect, sub-vect, and scale-vect that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar: $$ \begin{aligned} \left(x_{1}, y_{1}\right)+\left(x_{2}, y_{2}\right) &=\left(x_{1}+x_{2}, y_{1}+y_{2}\right) \\ \left(x_{1}, y_{1}\right)-\left(x_{2}, y_{2}\right) &=\left(x_{1}-x_{2}, y_{1}-y_{2}\right) \\ s \cdot(x, y) &=(s x, s y) \end{aligned} $$
Problem 49
Use segments \(\rightarrow\) painter to define the following primitive painters: a. The painter that draws the outline of the designated frame. b. The painter that draws an " \(X\) " by connecting opposite corners of the frame. c. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame. d. The wave painter.
Problem 53
What would the interpreter print in response to evaluating each of the following expressions? (list 'a 'b 'c) (list (list 'george)) \((\) cdr ' \(((x 1 \times 2)(y 1\) y2 \()))\) \(\left(\right.\) cadr \(^{\prime}((x 1 \times 2)(y 1\) y2 \(\left.))\right)\)
Problem 54
Two lists are said to be equal? if they contain equal elements arranged in the same order. For example, (equal? '(this is a list) '(this is a list)) is true, but (equal? '(this is a list)' (this (is a) list)) is false. To be more precise, we can define equal? recursively in terms of the basic eq? equality of symbols by saying that a and b are equal? if they are both symbols and the symbols are eq?, or if they are both lists such that (car a) is equal? to (car b) and (cdr a) is equal? to (cdr b). Using this idea, implement equal? as a procedure. \({ }^{36}\)
Problem 56
Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule $$ \frac{d\left(u^{n}\right)}{d x}=n u^{n-1}\left(\frac{d u}{d x}\right) $$ by adding a new clause to the deriv program and defining appropriate procedures exponentiation?, base, exponent, and make-exponentiation. (You may use the symbol \(* *\) to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself.
Problem 58
Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which \(+\) and \(*\) are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate. a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as \((x+(3 *(x+(y+2))))\). To simplify the task, assume that \(+\) and \(*\) always take two arguments and that expressions are fully parenthesized. b. The problem becomes substantially harder if we allow standard algebraic notation, such as \((\mathrm{x}+3 *(\mathrm{x}+\mathrm{y}+2))\), which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates, selectors, and constructors for this notation such that our derivative program still works?
Problem 59
Implement the union-set operation for the unordered-list representation of sets.
Problem 61
Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.
Problem 62
Give a \(\Theta(n)\) implementation of union-set for sets represented as ordered lists.
