1 Guidelines
2 Assignment
2.1 Some Textbook Problems
2.2 Writing Implements
2.3 Low-degree Polynomials
2.4 Derivative
2.5 Binary Tree
2.6 Mirror
2.7 Containment

Assignment 1, CSC430, Winter 2011

1 Guidelines

For this and all remaining assignments, every function you develop must come with the following things:

For this assignment, you must develop your solutions using the ’plai’ language. 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 Some Textbook Problems

Solve the following two problems from the textbook How To Design Programs, available online at www.htdp.org:

  1. Problem 2.3.3

  2. Problem 3.3.5. Use the value 9.8 for g.

2.2 Writing Implements

Here is a data definition for writing implements:

  ; Represent a writing implement
  (define-type writer
    ; ink volume in ml, how-full a number in the range 0.0 to 1.0
    [pen (ink-volume number?) (how-full number?)]
    ; length in cm
    [pencil (length number?)])

Develop the function how-far-to-write, which accepts a writing implement and returns the distance (in meters) that the implement will write before it’s done. Assume that pens can write 150 meters for each ml of ink left in the tank, and that pencils write 56 meters for each remaining cm of length.

2.3 Low-degree Polynomials

Develop a data definition for a polynomial that includes variants for linear (Ax + B) and quadratic (Ax^2 + Bx + C) polynomials of one variable. Call the variants linear and quadratic; each should accept the coefficients in the order given here (i.e., A comes first). For the purposes of this and the next problem, you should assume that the first coefficient (A) of a quadratic polynomial is never zero. The first coefficient of a linear polynomial, however, may be zero.

Next, define the function eval that accepts a polynomial and a value for the variable and produces the result of plugging in the value for the variable.

2.4 Derivative

Using the data definition you developed in the last problem, develop the function derivative that accepts a polynomial and returns another polynomial that represents its derivative. Ensure that your derivative function does not return a quadratic polynomial whose first coefficient is zero.

2.5 Binary Tree

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

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

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 at least one of its leaves.