# Homework 2 (Due Monday 1/31/11 at 10:00 am)

Submit via OWLSPACE in a single (`.ss`

or `.rkt`

) file that is runnable in DrScheme (so all expository answers must be enclosed in comment blocks or commented out using semi-colons.s into one file and submit this one compressed file. We did not deduct any points for using the wrong format on HW01 but we will deduct points for this error on this assignment. Begin each problem with a comment line containing the number of the problem.

The type "natural number" (**N**) in this assignment means the *natural-number* type defined in the text in Section 11.1. Your file should include a data definition for **N**. Unless the problem statement stipulates otherwise, the *only* built-in operations you may use with values of this type or variants (such as `natural>=1`

) are the constructors, accessors, and recognizers for the type and the `equal?`

(or `=`

}) operation. For **N**, the constructor is `add1`

; the accessor is `sub1`

, and the recognizers are `zero?`

and `positive?`

.

For variants, the constructor is typically `add1`

(unless the variant consists of multiples of `m > 1`

[such as the even numbers]), the accessor is typically `sub1`

, and the recognizers are typically `(equal? ... k)`

, where `k`

is the base number, and `(> ... k)`

.

## Problems from the book (HTDP) with some customization

- 11.2.4 (20 pts.)
- Copy the definition of
`deep-list`

from the text. Be sure to provide your own function template for`deep-list`

and to write template instantiations for`depth`

and`make-deep`

.

- Copy the definition of
- 11.4.7 (20 pts.)
- Include a data definition (following the text) of
`natural>=1`

. In addition to the constructors, accessors, recognizers, and`equal?`

, you may use the library functions`remainder`

and`*`

. Hint: define an auxiliary function`is-divisible-by`

of two inputs`p`

and`q`

(using the`remainder`

library function) that determines if`p`

is divisible by`q`

(*i.e.*, p/q is a whole number). - Note that the problem as stated in the book has TWO parts; the second, writing
`prime?`

is easy after doing the first. Do not worry about optimizing the search for a divisor for n by bounding the search to numbers less or equal to`(integer-sqrt n)`

; for simplicity, the`integer-sqrt`

and`sqrt`

library functions are forbidden in this exercise.

- Include a data definition (following the text) of
- 12.2.2 (20 pts.)
- 12.4.2 (30 pts.)
- Do this problem followed by developing the function
`arrangements`

that returns a list containing all of the arrangements (permutations) of the input word. This function is described in detail in the text and the code for it is**given to you**in the statement of problem 12.4.1. You are expected to present this answer in your program file as if you developed it, including supporting test data. - The
**Hint**for this problem should include the following:- Your program must distinguish between the types
*word*and*list-of-word*and process them separately. The data-driven approach to program design preached in this course naturally leads to this distinction. - The behavior of the function
`insert-everywhere/in-all-words`

is more easily understood given the following examples:(insert-everywhere/in-all-words 'd (list (list 'e 'r))) = (list (list 'd 'e 'r) (list 'e 'd 'r) (list 'e 'r 'd)) (insert-everywhere/in-all-words 'd (list (list 'e 'r) (list 'r 'e))) = (list (list 'd 'e 'r) (list 'e 'd 'r) (list 'e 'r 'd) (list 'd 'r 'e) (list 'r 'd 'e) (list 'r 'e 'd))

- You will need to write a help function
`insert-everywhere`

where`(insert-everywhere s w)`

inserts the letter`s`

in each possible position in the word`w`

, including*before*and*after*all letters of`w`

. Note the difference in the type contracts for`insert-everywhere`

and`insert-everywhere/in-all-words`

.

- Your program must distinguish between the types
- Notes: the function
`arrangements`

computes all of the**permutations**of the input word. Permutation is an important concept in basic probability theory. For some reason, the authors of the book chose to avoid using the relevant mathematical terminology. This problem includes writing the`arrangements`

function because it is cool and developing`insert-everywhere/in-all-words`

is the bulk of the work involved in developing`arrangements`

.

- Do this problem followed by developing the function
- 13.0.5 (part 4 only) (5 pts.)
- 13.0.8 (part 2 only) (5 pts.)