...
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 fordeep-list
and to write template instantiations fordepth
andmake-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, andequal?
, you may use the library functionsremainder
and*
. Hint: define an auxiliary functionis-divisible-by
of two inputsp
andq
(using theremainder
library function) that determines ifp
is divisible byq
(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, theinteger-sqrt
andsqrt
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.)
[In Second Edition, exercises 171 & 172]- 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 Hintfor 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:Code Block (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 letters
in each possible position in the wordw
, including before and after all letters ofw
. Note the difference in the type contracts forinsert-everywhere
andinsert-everywhere/in-all-words
.
- 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 thearrangements
function because it is cool and developinginsert-everywhere/in-all-words
is the bulk of the work involved in developingarrangements
.
- Do this problem followed by developing the function
- 13.0.5 (part 4 only) (5 pts.)
- 13.0.8 (part 2 only) (5 pts.)