CSC 270
Homework 2
Assigned 14 Sept, due 23 Sept

This assignment is to be done in PLT Scheme/Racket. You should get at least some of these functions written in class on Sept. 16, and do the rest on your own time. You are encouraged to do this in teams of two, both students working together on each function; if you do this, turn in one homework with both names on it.

For all functions, follow the design recipe: each function must have a contract, a good collection of test cases, and a function definition.

In order to get your homeworks graded quickly, I won't actually grade every one of these problems, but rather a sample including problems of various levels of difficulty. The rest are practice. If there's one that you want to make sure I look at, call my attention to it when you turn in the homework.

    Polymorphic data definition

    Switch languages to PLAI for the following exercises, which are intended to be done using define-type and type-case. Note that PLAI doesn't have check-expect, but has several other built-in forms for testing; look them up in the Help Desk.

  1. Define a data type vehicle with three variants:

    Define a function range which takes in a vehicle and tells how far it can go, as follows: the range of an automobile is its fuel capacity times its fuel efficiency; the range of a solar-car is its top speed times 12 (hours of sunlight); and the range of a bicycle is 50 miles.

  2. Define a data type shape with two variants:

    Define a function area which takes in a shape and returns its area.

    Define a function contains? which takes in a shape and a posn and tells whether the posn is inside the shape.

    Modify your data definition so there's a third variant:

    Modify your area and contains? functions to work correctly for this new variant.
    Note: For area, you may assume that the two shapes of a union don't overlap, so you can just add their areas. (Otherwise this becomes a complicated geometry problem, and that's not what I want you to worry about right now.) For contains?, your function should work correctly regardless of whether the two shapes overlap.

  3. Define a data type river with three variants:

    Define a function volume that takes in a river and returns the total amount of water flowing out of it (in gallons per hour). This is obvious for a spring. For a section, the volume is the same as the volume at the far end (let's pretend there's no evaporation). For a branch, the volume is the sum of the volumes of the two branches.

    Define a function max-length that takes in a river and returns the longest distance to any spring.

  4. Functions on Scheme lists

    You can do these exercises in either PLAI, Beginner, or Beginner with List Abbreviations language.

  5. Write a function add-up which takes in a list of numbers and returns the sum of the numbers.

  6. Write a function any-matches? which takes in a string and a list of strings, and tells whether the string matches any of the strings in the list.

  7. Write a function count-matches which takes in a string and a list of strings, and tells how many list elements match the string (possibly 0).

  8. Write a function count-over which takes in a number and a list of numbers, and tells how many list elements are larger than the specified number.

  9. Write a function average that takes in a list of numbers and returns their average. For a first version of this function, you may assume there is at least one number in the list. For full credit, your function should generate an appropriate and user-friendly error message for the empty-list case.

  10. Write a function convert-reversed that takes in a list of numbers (which you may assume are all integers in the range 0-9), interprets them as digits in a decimal number, ones place first (trust me, this makes it easier!), and returns the number they represent. For example, (convert-reversed (list 3 0 2 5)) should be 5203.

  11. Write a function dollar-store? that takes in a list of numbers -- the prices of things at a store -- and tells whether or not everything in the store is priced under a dollar.

  12. Write a function multiply-all that takes in a list of numbers and returns their product. Hint: What is the "right answer" for the empty list? It may not be what you think at first!

  13. Write a function largest that takes in a non-empty list of numbers and returns the largest one. Hint: There are several possible ways to handle the empty case....

  14. Write a function total-votes that takes in a list of candidate structures (from homework 1) and returns the total number of votes cast.

  15. Write a function winner that takes in a list of candidate structures and returns the name of the winner, or the word "tie" if there was a tie for first place. (How do you want to handle the empty-list case? I guess we could call it a "tie"....)

  16. Write a function square-each that takes in a list of numbers and returns a list of their squares, in the same order. For example,
    (square-each (list 4 -3 1 12)) should return (list 16 9 1 144).

  17. Write a function substitute that takes in two strings and a list of strings, and returns a list the same length as the given list, but with all occurrences of the first string replaced by the second. For example,
    (substitute "old" "new" (list "this" "that" "old" "new" "borrowed" "old" "blue")) should return
    (list "this" "that" "new" "new" "borrowed" "new" "blue")

  18. Write a function remove-first that takes in a string and a list of strings, and returns the same list but with the first occurrence (if any) of the given string removed. For example,
    (remove-first "old" (list "this" "that" "old" "new" "borrowed" "old" "blue")) should return
    (list "this" "that" "new" "borrowed" "old" "blue").

  19. Functions on trees

  20. Define a data type bst (short for "binary search tree") with two variants:

  21. A proper bst is one in which every node's value is larger than any of the numbers in its left bst, and smaller than any of the numbers in its right bst.
    Define a function proper-bst? which takes in a bst and tells whether it is proper.

  22. Define a function in-bst? that takes in a number and a proper bst, and tells whether that number appears in the bst. Hint: use the assumption that the bst is proper to help you efficiently find the number, if it's there, or know for certain that it isn't there.

  23. Define a function path-to that takes in a number and a proper bst, and returns a list of node values encountered on the way from the root of the tree to the number in question (or to where it would be if it were there). The list should end with the desired number if it was in the tree.

  24. Define a function insert that takes in a number and a proper bst, and returns a proper bst just like the given one, but containing the specified number. If the number was already there, you may return the exact same bst.

  25. Define a function make-bst that takes in a list of numbers and returns a proper bst containing exactly those numbers. [I left out the word "proper" when I originally gave this assignment.]


  26. Last modified: 
    Stephen Bloch / bloch@adelphi.edu