Problem Set 11
Purpose This problem set concerns the design of generative recursive functions and functions with accumulators.
Finger Exercises HtDP/1e: 29.3.4 (stepper), 29.3.5, 31.3.3, 31.3.4, 31.3.5, 31.3.6, 31.3.7
Problem 1 Exercise 28.1.6
Problem 2 Exercise 29.3.7, 29.3.8
Problem 3 Here is a vector-based graph representation:
Translate the graph from figure 78 into this data representation.
Design the function draw-graph, which consumes a Graph and produces an Image of the graph. Use straight black lines to connect nodes in this graph image; don't try to construct arrows.
Design the function find-route for this graph representation. The function consumes a graph and two indicies into the graph: from and to . If there is a path from the former to the latter, it produces the list of Posns for the nodes that must be visited; otherwise it produces false.
Design the function draw-route. The function consumes a Graph and a Path. It produces an image of the graph with the route colored in red.
Problem 4 Design the function dc-sum, which consumes a vector of numbers and produces its sum. It ``divides'' (its view of) the vector in the middle until it reaches a slice of three slots or fewer. Then it adds the numbers in these slots. As the function returns, it ``conquers'' these slices by adding the results.
Is this function faster than a vector-sum that proceeds from left to right? Is it faster if each ``slice'' computation is run in parallel?
Problem 5 Exercise 32.1.1 from HtDP/1e