Assignment 1, CSC430, Spring 2008
1 Guidelines
For this and all remaining assignments, every function you develop must come with the following things:
A commented header line that expresses the result of the function in terms of its inputs, written in English. Be as precise as you can within the space of a line or two.
A commented contract line that gives the types of the inputs and the output. The contract should have the form <in-type> ... -> <out-type>. So, for instance, a numerical square function might have the contract line:
; number -> number
Test cases. A function without test cases is incomplete. Write the test cases first, please.
For this assignment, you must develop your solutions using the Programming Languages: Application and Interpretation: Restricted PLAI Scheme language level. Your test cases must use the (test ...) form.
Your solution should take the form of a single file. Solve each problem separately, ands make sure that each solution appears in a separate part of the file, with comments separating each problem’s solution.
Hand in your solution using the handin server. For help with the handin server, please see the course web page.
2 Assignment
2.1 Problem
Solve the following two problems from the textbook How To Design Programs, available online at www.htdp.org:
2.2 Problem
Here is a data definition for payment information that a store might use to associate payments with inventory items.
; Represent a payment made to a store. |
(define-type payment |
[cash (amt number?)] ; amt is number of cents |
[credit (amt number?) (id string?)] ; amt is number of cents |
[theft (item string?) (cashier string?)]) |
Develop the function income, which consumes a payment and returns the amount of money generated by the payment (in the case of theft, this should be zero).
Develop a data definition for a point that includes variants for 2d, 3d, and 4d points. Call the variants 2dpoint, 3dpoint, and 4dpoint. Include a define-type and at least four examples of the data.
2.3 Problem
Using the data definition you developed in the last problem, develop the dist-from-zero function that accepts a point and returns a number representing the distance from the origin to the given point (using a standard Euclidean distance metric).
2.4 Problem
Develop a data definition for a binary tree with symbols at the leaves but no values at the interior nodes. Its variants should be named leaf and node. Include a define-type and at least three examples of the data.
2.5 Problem
Using the data definition you developed in the last problem, develop the mirror function that accepts a binary tree and produces a new binary tree that is the left-right mirror image of the first one. That is, if the input tree has the symbol 'horse at the far left of the tree, the new one should have the symbol 'horse at the far right of the tree.
2.6 Problem
Using the same data definition, develop the contains? function that accepts a binary tree and a symbol and returns true exactly when the given tree contains the given symbol at one of its leaves.