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.

Data descriptions for this homework

A letter is a one-character string containing a single lowercase letter.

A tile is either:

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:

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.

Finger Exercises

For this homework I am recommending the following finger exercises:

Problems to submit

  1. 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

  2. Two 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.

Karma problem

  1. Define a function that consumes a list of stations and produces a 1D-tree containing those same stations. The 1D-tree must be balanced, which in this case means that its depth must be at most one more than the base-2 logarithm of the number of stations.