Programming Warmup, CSC430, Fall 2024🔗

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,

• type declarations for argument and return types, and

• 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 typed/racket language. Your test cases must use the (check-equal? ...) or (check-= ...) form. Use check-= to check for equality of numbers, especially when they can be inexact (floating-point) numbers.

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.

1.1 Mutation🔗

There’s no need for mutation in any of the first three assignments in this class. Don’t mutate bindings, and don’t mutate structure fields. Not sure what this means? That’s okay, just don’t call functions that have "set" and an exclamation point (bang) in them.

1.2 A note on Numbers🔗

For this assignment (as well as all the others), there’s no need for complex numbers. Accordingly, you should use the type Real rather than the type Number. This will save you some hassle in using the check-= form that checks for numeric near-equality.

2 Assignment🔗

2.1 Some Textbook Problems🔗

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

1. Problem 2.3.3

2. Problem 3.3.3

Note: These problems come with solutions. I would encourage you to write your own solutions first, including all of the steps of the design recipe. Then, go ahead and take a look at the ones linked to on the web page.

2.2 Fruits🔗

Here is a data definition for fruits:

Develop the delicious? function, that accepts a food and returns whether or not it is delicious. A blueberry is delicious if its blueness is higher than 5, and the count is greater than or equal to 100. Bread is delicious if its hydration is between 0.7 and 0.9, inclusive. Bananas are always delicious.

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 full binary tree called BTree with symbols in each node but no values at the leaves. Its variants should be named Leaf and Node. Every node has exactly two children. The symbol should be the first argument to your Node structure. 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 Left-Spine🔗

Using the BTree data definition, develop the left-spine function that accepts a binary tree and returns a new one which has only the “left spine” of the given tree, and each right branch is simply a leaf.

To be more specific: the “left spine” of a tree is the set of nodes reachable by starting at the root and following zero or more “left child” links.

2.8 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 in at least one of its nodes.

2.9 Occurrences🔗

Using the same data definition, develop the occurrences function that accepts a binary tree and a symbol and returns a number indicating how many nodes in the tree have the given symbol as their value.

2.10 Substitution🔗

Using the same data definition, develop the subst function that accepts a source BTree and a symbol and a replacement BTree and returns a new tree where every node of the source tree containing the symbol is replaced (along with all of its descendants) by the replacement tree. (Make sure the source tree is the first argument to the subst function, or my tests will all fail....)

2.11 All Path Lengths🔗

OPTIONAL: Using the BTree data definition, develop the all-path-lengths function that accepts a binary tree and returns a list containing the lengths of all of the paths from the root to each leaf. A tree that is simply a leaf has a single path length of zero.

This problem will probably require one or more helper functions; try to make sure that your helper functions are well-named, with good purpose statements.