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:

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 (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 
(define (grade* l)
  (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:

;; best-homework-grade : [Listof Grade] -> Grade
(define (best-homework-grade 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

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)