Homework 6 - Descendant Trees; Higher-Order Functions

CS 1101 - A-term 12

Homework 6 - Variable-width Trees; Higher-Order Functions

Due: Tuesday, October 2 at 5pm

Assignment Goals

To make sure you can write data definitions for variable-width trees.
To make sure you can write programs over variable-width trees.
To make sure you can use filter and map to simplify the development of certain list problems.

The Assignment

There are two parts to this assignment. In Part 1, you will define data and functions for a variable-width tree. In Part 2, you will use map and filter to re-write some of the list functions we developed a couple of weeks ago.

Problems

Part 1

A river system can be represented as a hierarchy of tributaries. For example, a partial list of the tributaries that feed into the Missouri River include the Jefferson, Sun, Yellowstone, Madison, and Gallatin Rivers. The Jefferson, in turn, is fed by the Beaverhead and Big Hole rivers. The Yellowstone is fed by the Gardner, Sheilds, and Boulder rivers, and so on. In this set of exercises you will create a data definition for a river and its tributaries, and write programs that answer questions about the quality of the water in the rivers.

Assume that for each river, measurements of the river's pH and DO (dissolved oxygen) levels are available. Such measurements are taken at the confluence of the rivers (the point at which the tributaries converge). pH levels can range from 0 (most acidic) to 14 (most alkaline). The normal range for bodies of water are 6.5 - 8.5. DO is measured in parts per million (ppm), and can range (at sea level) from 0 ppm (the lowest amount of dissolved oxygen) to 12ppm (saturation point).

Provide data definitions for a river system. For each river in the hierarchy, you should record the following information: the name of the river, the pH of the water, the DO in parts per million, and a list of the tributaries (rivers) that feed into the river.
Provide an example of a river system that starts with a single river and consists of at least two levels in the hierarchy below that. You may use the example given above for the Missouri River, if you wish. (You may make up numbers for pH and DO - for these exercises we're not concerned about the accuracy of the information, just that you can provide a correct model for the information.)
Provide the templates for your data definitions.
Develop a function lower-ph-than that consumes a river system and a number. The function produces a list of the names of each river in the given system that has a pH value lower than the given pH.
Develop a function healthy? that consumes a river system and produces a boolean. The function returns true if every river in the system has a pH between 6.5 and 8.5, and a DO of at least 6ppm.
Acid rain can lower the pH of water in a river system. Develop a function lower-all-ph that consumes a river system and produces a river system. The river system that is produced is the same as the original, except that the pH of all the rivers in the system have been lowered by 0.1.

Part 2

In Homework 4 we developed several functions that were designed to process a list of items in an online auction. As you solve the following problems, you may refer to and use any of the answers to the HW4 problems. Start by copying and pasting the data definitions for bid, item, and list-of-item from the given solutions to your DrRacket Definitions window.

Using map and/or filter, redefine the function hour-passed, that has the following contract and purpose:

;; hour-passed:  auction -> auction
;; consumes an auction and produces an auction in which the hours left on each biddable item
;; has been decreased by one.  If the number of hours left is zero, the number of hours remain
;; at zero

Using map and/or filter, redefine the function expiring-within, that has the following contract and purpose:

;; expiring-within:  auction number -> auction
;; consumes an auction and a number and produces a list of all items that expire within 
;; the given number of hours

Using map and/or filter, write a new function list-person-bids, that has the following contract and purpose:

;; list-person-bids:  auction string -> list-of-bid
;; consumes an auction and the name of a bidder and produces a list of all the
;; bids in the auction for the named person

What to Turn In

Here is the grade sheet that the TAs will use when they grade this assignment.

Using web-based turnin, turn in a single file containing all code and documentation for this assignment. Name your file according to the naming conventions for files. Make sure both partners' names and wpi login names appear in a comment at the top of the file.