in Books, Concrete Abstractions, Doing Books

Concrete Abstractions: Chapter 12

Exercise 12.4: Draw a tree, analogous to Figure 4.4 on page 92, showing how the value of C(4, 2) is computed by choose. Your tree should have C(4, 2) at the root and six 1s as its leaves.

Exercise 12.6: Using these procedures, write
a. A procedure called table-fill! that takes a table and an element and sets every entry in the table to the given element. For example, (table-fill! table 0) would have a similar effect to that of zero-out-vector! in Section 11.6.
b. A procedure called display-table that nicely displays its table parameter.



Exercise 12.31: Imagine the following game: You are given a path that consists of white and black squares. The exact configuration of white and black squares varies with the game. You start on the leftmost square (which we’ll call square 0), and your goal is to move off the right end of the path in the least number of moves. However, the rules stipulate that:
If you are on a white square, you can move either 1 or 2 squares to the right.
If you are on a black square, you can move either 1 or 4 squares to the right. […]
Write a memoized version of fewest-moves.

Exercise 12.33: The function h(n) is defined for nonnegative integers n as follows:
h(n) = \begin{cases} 1 & \text{ if } n<2\\ h(n-1) + h(n-2) & \text{ if n } < \text{2 and n is odd}\\ h(n-1) + h(n/2) & \text{ if n } \geq \text{2 and n is even}\\ \end{cases}
a. Write a dynamic programming procedure for efficiently calculating h(n).
b. Is it possible to modify the procedure so that it stores all the values it needs in a vector of fixed size, as walk-count can be modified to store the values it needs in a two-element vector? (A vector of “fixed size” is one with a size that does not depend on the parameter, n.) Justify your answer.
Solution: a & b. I implemented b directly into the code.

Write a Comment


This site uses Akismet to reduce spam. Learn how your comment data is processed.