 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 200word 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 miniproject. 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:
 "structural recursion"
 "generative recursion"
 "using loops"
 "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:
 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) ...) 

removeedge  Graph Symbol Symbol > Graph 
 create a graph like G without an edge
between A and B 
 (define (removeedge G A B) ...) 
All nodes of the graphs are labeled with symbols.

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 .

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 nonexisting 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:
As you know, your final grade is a weighted average of your exam grades,
your quiz grades, and your homework grades:
(define WHIM .0)
;; Grade is Posn:
;; the first number represents your score,
;; the second one the maxiumum score
;; grade : Grade Grade [Listof Grade] [Listof Grade] > Number
(define (grade mid1 mid2 lqu lhw)
(local ((define exam (* 60 (grade* (list mid1 mid2))))
(define hmwk (* 25 (besthomeworkgrade 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
(define (grade* l)
(local ((define scr (apply + (map posnx l)))
(define max (apply + (map posny 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:
;; besthomeworkgrade : [Listof Grade] > Grade
(define (besthomeworkgrade lhw)
(local ((define scenarios (all lhw))
(define grades (map grade* scenarios)))
(apply max grades)))
Put differently, we compute all possible homework grades and take the
best possible one.
Your tasks are

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.

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? (besthomeworkgrade (list (makeposn 0 10)
(makeposn 10 20)
(makeposn 30 30)))
.8)
(equal? (grade* (list (makeposn 20 50) (makeposn 30 50)))
.5)
(equal? (grade (makeposn 50 50) (makeposn 50 50)
(list (makeposn 1 1)
(makeposn 1 1)
(makeposn 1 1)
(makeposn 1 1)
(makeposn 1 1)
(makeposn 3 3)
(makeposn 1 1)
(makeposn 10 10)
(makeposn 2 2))
(list (makeposn 10 10)
(makeposn 20 20)
(makeposn 30 30)
(makeposn 40 40)))
95)
