Homework Three

Due 8:00am Monday, June 11th, 2001. 8:00AM.

Problem 1
5 points
Make the list representation of this cons cell diagram.

+---+   +---+   +---+   +---+   +---+
|A|-|-->|B|-|-->| |-|-->|3|-|-->| |/|
+---+   +---+   +---+   +---+   +---+
                 |               |
                 |              +---+
                 |              |Y|/|
                 |              +---+
                 |
                +---+   +---+   +---+
                |B|-|-->| |-|-->| |/|
                +---+   +---+   +---+
                         |       |
                         |       |
                        +---+   +---+
                        |7|9|   | |/|
                        +---+   +---+
                                 |
                                 |
                                +---+
                                |Z|/|
                                +---+

For example:

 +---+
 |Z|/|
 +---+

Would be answered like this:

(define (p1) '(Z))

Problem 2
15 points
You get to play Black Jack Casino Dealer today! The object of this function is to shuffle two decks of cards. You function should be named shuffle and take in two lists of cards to be shuffled together. For example:

> (Shuffle '(4s 5s 6s 7s 8s) '(9d 10d Jd Qd Kd))
(4s 9d 5s 10d 6s Jd 7s Qd 8s Kd)

> (Shuffle '(Ac 2c 3c) '(Ah Kh Qh Jh 10h 9h))
(Ac Ah 2c Kh 3c Qh Jh 10h 9h)

> (Shuffle '(Ac As Ad Ah) '())
(Ac As Ad Ah)

> (Shuffle '() '())
()

Problem 3
15 points
In this function you want to take a list and remove all duplicate items. Name the function remove-duplicates. It will take in one parameter: the list of items to remove the duplicates from. Keep the first occurance of the element and remove all of the rest. For example:

> (remove-duplicates '(a b b r a c a d a b r a))
(a b r c d)

> (remove-duplicates '(1 1 1 1 1))
(1)

> (remove-duplicates '(one of these things does not belong here here))
(one of these things does not belong here)

Problem 4
15 points
The next problem is for all you history majors out there. Bet you never thought computers could relate to history! Danielle the Historian needed to keep trace of research data about the Black Plague so she came up with this data structure.

  '((Rome   (4903 1900))
    (Munich (1321 500) )
    (Vienna (2130 1700))
    (Paris  (6200 1322))
    (London (5100 2211)))

This structure holds a list of cities hit by the plague. The numbers that are associated with the cities are the before and after population. Since Danielle wants to be able to search this data structure, the first function you must write is called plague-data-for. This function will be passed the name of city to search for and the data structure that holds the city info. IF the city is not in the list, then return false. NOTE: your function must work for any data structure we pass in that's formatted like the one shown above. YOU MAY NOT USE THE FUNCTION ASSOC IN YOUR SOLUTION Sample usage:


> (plague-data-for 'Paris  '((Rome   (4903 1900))
			     (Munich (1321 500) )
			     (Vienna (2130 1700))
			     (Paris  (6200 1322))
			     (London (5100 2211))))
(Paris (6200 1322))

> (plague-data-for 'Miami  '((Rome   (4903 1900))
                             (Munich (1321 500) )
			     (Vienna (2130 1700))
 			     (Paris  (6200 1322))
			     (London (5100 2211))))
#f

Problem 5
5 points
To make this data structure even more useful you need to write another function called population-data-for that will return the populations for a city.

> (population-data-for 'Vienna  '((Rome   (4903 1900))
			          (Munich (1321 500) )
			          (Vienna (2130 1700))
			          (Paris  (6200 1322))
     			          (London (5100 2211))))

(2130 1700)

> (population-data-for 'Vancouver  '((Rome   (4903 1900))
				     (Munich (1321 500) )
				     (Vienna (2130 1700))
				     (Paris  (6200 1322))
				     (London (5100 2211))))
#f

Problem 6
5 points
Now write another function to get the before plague population. Name it before-plague.

; (before-plague 'Munich  '((Rome   (4903 1900))
			    (Munich (1321 500) )
			    (Vienna (2130 1700))
			    (Paris  (6200 1322))
			    (London (5100 2211))))
1321

; (before-plague 'Tokyo  '((Rome   (4903 1900))
                              (Munich (1321 500) )
                              (Vienna (2130 1700))
                              (Paris  (6200 1322))
                              (London (5100 2211))))
#f

Problem 7
5 points
You still need one more function, write after-plague

> (after-plague 'Munich  '((Rome   (4903 1900))
                              (Munich (1321 500) )
                              (Vienna (2130 1700))
                              (Paris  (6200 1322))
                              (London (5100 2211))))
500

> (after-plague 'Moon-Base-One  '((Rome   (4903 1900))
                                     (Munich (1321 500) )
                                     (Vienna (2130 1700))
                                     (Paris  (6200 1322))
                                     (London (5100 2211))))
#f

Problem 8
15 points
After approving you work so far, Danielle asks you to write one last function for her. She now needs to calculate the number of deaths caused by the plague. She wants you to write sum-of-deaths which takes in two parameters, one is a list of cities that are to have their population losses calculated and the other is the data structure. The return value of this needs to be a list of dotted pairs of the city names and population losses. (all cities will be valid)

> (sum-of-deaths '(Rome Paris London)  
                    '((Rome   (4903 1900))
                      (Munich (1321 500) )
                      (Vienna (2130 1700))
                      (Paris  (6200 1322))
                      (London (5100 2211))))
((Rome . 3003) (Paris . 4878) (London . 2889))

Problem 9
25 points: 15 for just averaging the grade, 10 for pro-rating it.
Here is where you get to really do something useful! Write a function called my-average which works just like you might think. It is passed a list grades and it calculates the average. It takes a list of tests, labs, homeworks, and the grade on the final. From reading the syllabus you know what each catagory is worth. You must also pro-rate the grade if there happend to be no grades in one catagory.

> (my-average '(98 81 89) 
              '(100 100 60 100 100 0 100 100 100 100)
              '(97 88 90 73 95 85 91 69)
               83)
86.1

> (my-average '() '() '() 0)
#f

> (my-average '(87) '(100 100 80) '(90 92) 0)
89.78571428571428

> (my-average '() '(100 100 80) '(90 92) 0)
91.875