CS 1101 - C-term 12

Homework 5 - Descendant Trees; Higher-Order Functions

Due: Tuesday, February 21 at 5pm

Read the expectations on homework.

Assignment Goals

The Assignment

There are two parts to this assignment. In Part 1, you will define data and functions for a descendant 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).

For this assignment, latitude and longitude can be expressed as whole numbers (0-90 for latitude, 0-180 for longitude) followed by a designation of north or south, east or west (so, for example, Worcester is at 42 N, 71 W).

  1. Provide data definitions for a river system. For each river in the hierarchy, you should record the following information: the name of the river, its geographic latitude and longitude, the pH of the water, the DO in parts per million, and a list of the tributaries (rivers) that feed into the river. You should define a struct to represent the latitude and longitude information.

  2. 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. (Also, you may make up numbers for latitude, longitude, 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.)

  3. Provide the templates for your data definitions.

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

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

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

    The next problem is a little trickier than the preceding problems. We'll see how to solve this kind of problem on Monday (Feb 13). You won't have a problem like this one on Exam 2.

  7. Develop a function find-river that consumes a river system and the name of a river and produces the location (i.e. the latitude and longitude) of the named river. You may assume that a river with the given name exists in the river system.

Part 2

In Homework 3 we developed several functions that were designed to process a list of ads. As you solve the following problems, you may refer to and use any of the answers to the HW3 problems. Start by copying and pasting the data definitions for ad and list-of-ad from the given solutions to your DrRacket Definitions window.

Problems 8, 9, and 11 can be solved using filter. We'll see how to solve problem 10 on Monday.

  1. Using map and/or filter, redefine the function count-political-ads, that has the following contract and purpose: 
    ;; count-political-ads:  list-of-ad -> number
;; consumes a list of ads and produces the number of ads in the list that are political
    (Hint: You may use the DrRacket built-in function called length that returns the number of items in a list.)

  2. Using map and/or filter, redefine the function primetime-ads, that has the following contract and purpose: 
    ;; primetime-ads:  list-of-ad -> list-of-ad
;; consumes a list of ads and produces a list of all the ads occurring in primetime

  3. Using map and/or filter, redefine the function politicians-sponsoring-ads, that has the following contract and purpose: 
    ;; politicians-sponsoring-ads: list-of-ad -> list-of-string
;; consumes a list of ads and produces a list of strings. The list that is produced contains the names of the politicians who have political ads 
;; (it's OK if the resulting list contains duplicate names).

  4. Using map and/or filter, write a function expensive-ads, that has the following contract and purpose: 
    ;; expensive-ads:  list-of-ad number -> list-of-ad
;; consumes a list of ads and a number. The function produces a list of those ads for which the total ad cost exceeds the given number.

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.