Assignment 1, CSC430, Spring 2016
1 Guidelines
For this and all remaining assignments, every function you develop must come with the following things:
A commented purpose statement 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 type comment of the form (: name (type .. -> type))
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 racket language. Your test cases must use the (check-equal? ...) 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:
2.2 Magic Tricks
Here is a data definition for magic tricks:
; represent a magic trick ; (define-type Trick (U Card-Trick Guillotine)) (struct Card-Trick (decks volunteers) #:transparent) (struct Guillotine (realism has-blood?) #:transparent)
Develop the function trick-minutes, that computes how long a trick will take. Assume that a card trick requires one minute per deck of cards and that its length is doubled for every volunteer required, and that a guillotine trick requires ten minutes unless it has blood, in which case it requires 20.
2.3 Low-degree Polynomials
Develop a data definition for a polynomial (with type name 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 interp 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 called BTree 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 Min-Depth
Using the BTree data definition, develop the min-depth function that accepts a binary tree and produces the length of the shortest path to a leaf. A single leaf has a min-depth of zero.
2.7 Traversal
using the same data definition, develop the in-order function that accepts a binary tree and produces a list representing an “in-order” traversal of the symbols at the leaves of the binary tree.