This homework is due at 11:59PM on Monday, October 7.
Submit your solutions in a single file using the COMP 50 Handin button on DrRacket; the homework is the lists
homework.
All the exercises should be done using the Beginning Student Language with list abbreviations.
A letter is a one-character string containing a single lowercase letter.
A tile is either:
(make-blank)
A station is a structure:
(make-station name distance)
where name
is a string and distance
is a number representing the distance in miles from Boston. You can get real-world information about stations on the Wikipedia page for the Northeast Corridor.
A 1D-tree of stations is either:
A station
A structure (representing a point on the line)
(make-point distance south north)
where
distance
is the distance of the point from Bostonsouth
is a 1D-tree of stations, all of which are further away from Boston than the given distance
north
is a 1D-tree of stations, all of which are closer to Boston than the given distance
In this homework, all lists are made with empty
and cons
as described in the book. Selector functions for the cons
case are first
and rest
.
For this homework I am recommending the following finger exercises:
Define a function that takes as arguments a distance in miles and a 1D-tree of stations, and which returns information saying the name of the nearest station, how far away it is, and in what direction. You must write a data definition that says how the information you return will be represented.
Use the design recipe for self-referential data (natural recursion). In addition, plan on writing some helper functions that operate on distances and stations. Use your wish list!
(With any luck, later in the term we will use a similar tree to help you locate US cities quickly.)
Hint: For purposes of testing, you will do well to define a function that takes a tree and two numbers lo
and hi
, and checks the given tree to be sure that
lo
and hi
point
in the tree, the stations south and north of that point are located at distances that are consistent with the distance of the pointTwo fisherman go out in a boat and use nets to pull a whole bunch of bluegills out of the Mystic Lakes. They agree to divide the catch evenly. You are given two buckets and two scales and are charged with placing the fish into the buckets, dividing evenly by weight. A friend of Mr Turing’s whispers to you that dividing as evenly as possible might take more time than you have. The fishermen agree that your time is worth something, and they will be content if you place one fish at a time in the fairest way possible.
To prove to the fishermen that your division of fish is reasonably fair, you will use “computational buckets”. A computational bucket not only holds a list of fish but also contains a readout that instantly gives the total weight of the fish in the bucket.
Write a data definition for a pair of computational buckets. The only important thing about a fish is its weight.
Define a function that takes as arguments a list of fish and returns a pair of computational buckets such that each bucket contains about the same weight of fish as the other bucket.
Use the design recipe for self-referential data (natural recursion).
It turns out that the fairness of your division can be strongly affected by the order in which you consider the fish. Please create a random list of 30 fish and run three experiments:
How do the experiments affect the fairness of the division?
A convenient way to report on the experiments is to produce a list of three strings, as in the following example:
> (three-experiments (N-random-fish 30))
`("When divided, randomly ordered fish give buckets that differ by [REDACTED]"
"When divided, increasing fish give buckets that differ by [REDACTED]"
"When divided, decreasing fish give buckets that differ by [REDACTED]")
Hint: to sort the fish, you will want to use the insertion sort defined in section 12.2 of the first edition textbook. You can develop a similar sort function that sorts in increasing order.