Problem Set 11

home work!

Programming Language ISL+

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

image

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.

Path Graph Node

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