Teaching 211 F '06 Assignments The Hand In The Recipes The World Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14

### Problem Set 13

Due date: 12/06 @ 6pm

Programming Language: Intermediate Student Language with lambda

Problem 0 [5%]:

Find one interesting article from the weeks news on the use of software/computers in society. Summarize the article in your own words with a single 200-word paragraph, as a pair, one playing writer, the other playing editor. Add both the article and the summary in with the rest of your problem set.

The goal of this last problem set is to practice what you have learned over the course of the semester with a mini-project. Both require planning and the careful design of functions. For full credit you must annotate each function with as many of the following notes as applicable:

1. "structural recursion"
2. "generative recursion"
3. "using loops"
4. "with accumulator"
You will get credit for each correct annotation and you will lose credit for each incorrect annotation.

Solve one of the problems A1 or A2. Do not solve both; you will not get extra credit for extra work.

Problem A3 is required.

As always, you must work in pairs.

Problem A1:

1. Design two distinct implementations of the following interface for directed graphs:
 `neighbors` `Graph Symbol -> [Listof Symbol]` determine the neighbors of `A` in `G` `(define (neighbors G A) ...)` `connected?` `Graph Symbol Symbol -> Boolean` is A directly connected to B in G? `(define (connected G A B) ...)` `remove-edge` `Graph Symbol Symbol -> Graph` create a graph like `G` without an edge between `A` and `B` `(define (remove-edge G A B) ...)`
All nodes of the graphs are labeled with symbols.
2. Design the function `route` to this interface, that is, the function may use only the above three functions to refer to graphs; it may not assume anything about the actual construction of graphs.

The `route` function consumes a graph and the names of two nodes: `F` and `T`. It produces the list of nodes that determine a sequence of edges from `F` to `T`, if it exists; otherwise, the function produces `false`.

3. Develop a stress test suite for your graph representations. Make up a graph with, say, 1000 nodes and between 50 and 500 random edges. Search for a long route and a non-existing route in the graph and time the performance. Report your results as suggested in homework 11.

Problem A2:

Design a program that create a firework display based on the keys that a user touches. That is, translate each key event into the launch of a rocket (with predetermined height, shape, unfolding). When there are no more rockets around, the program should shut down.

Here are two animated GIFs, which we produced from recent (ambitious) solutions for this homework problem:  (Charlotte Soesanto) (Alex Moore)

For the star shapes, you will need to download the most recent version of the `image.ss` teachpack and replace the existing one in ".../plt/collects/htdp/". Alternatively, download the new version of DrScheme (v360) and use it instead.

Problem A3:

``````
(define WHIM .0)

;; Grade is Posn:
;;  the first number represents your score,
;;  the second one the maxiumum score

(define (grade mid1 mid2 lqu lhw)
(local ((define exam (* 60 (grade* (list mid1 mid2))))
(define hmwk (* 25 (best-homework-grade lhw)))
(define quiz (* 10 (grade* lqu))))
(+ WHIM exam hmwk quiz)))
``````
The remaining 5% are up to the whim of the two instructors.

Naturally, the score of a list of grades is just the sum of your scores divided by the sum of the maximum scores:

``````
;; grade* : [Listof Grade] -> Number
(local ((define scr (apply + (map posn-x l)))
(define max (apply + (map posn-y l))))
(/ scr max)))
``````
Except for the homework score, of course. We promised that we drop the homework grade that drags down your grade the most:
``````
(local ((define scenarios (all lhw))
``````
Put differently, we compute all possible homework grades and take the best possible one.

1. to design the function `all`. It consumes a list of items and produces a list of list of items. The result list has as many copies of l as (length l) the first one misses the first element, the second one misses the second element, and .. the last one misses the last element.
2. to develop a test case that shows that dropping a homework grade doesn't necessarily mean dropping the worst grade (say a 0) but dropping the one with the worst impact on your overall score.

Test Suite:

``````
(equal? (best-homework-grade (list (make-posn 0 10)
(make-posn 10 20)
(make-posn 30 30)))
.8)

(equal? (grade* (list (make-posn 20 50) (make-posn 30 50)))
.5)

(equal? (grade (make-posn 50 50) (make-posn 50 50)
(list (make-posn 1 1)
(make-posn 1 1)
(make-posn 1 1)
(make-posn 1 1)
(make-posn 1 1)
(make-posn 3 3)
(make-posn 1 1)
(make-posn 10 10)
(make-posn 2 2))
(list (make-posn 10 10)
(make-posn 20 20)
(make-posn 30 30)
(make-posn 40 40)))
95)

``````

 last updated on Thu Nov 30 11:55:15 EST 2006 generated with PLT Scheme