Be sure you have Racket version 6.7 installed. You can download it from `https://download.racket-lang.org/` Racket is also installed on the tlab machines in `/home/software/racket/bin/drracket`.

Open DrRacket, set the language to “The Racket Language” (via the Language | Choose Language menu item), put the following program into the upper window (replacing whatever is there), and click “Run”

#lang plai (expt 2 100)You should see the prompt in the interactions window (a

Install the handin server plugin by using DrRacket’s **File | Install Package...** menu item. In the dialog box, paste this url into the box:

Then press

After restarting DrRacket, select the **Manage EECS 321 PL Handin Account...** menu item from DrRacket's **File** menu. Change to the **New User** panel, and pick a username and password. (Use your real name and real NetID, so that we can connect your homework submissions with you. **DON'T** reuse an existing password. Good password hygiene is important.)

You will have to install the handin plugin for each different filesystem for which you want to have a **Handin** button. However, after creating a handin account once from any machine, you can use DrRacket's **Handin** button on any other machine.

There is a quick reference to things Rackety available from the course webpage. You may wish to have a look if you're not familiar with Racket.

Every homework assignment you hand in must begin with the following definition (taken from the Provost's website; see that for a more detailed explanation of these points):

(define eight-principles (list "Know your rights." "Acknowledge your sources." "Protect your work." "Avoid suspicion." "Do your own work." "Never falsify a record or permit another person to do so." "Never fabricate data, citations, or experimental results." "Always tell the truth when discussing your work with your instructor."))

If the definition is not present, you receive no credit for the assignment.

The following `Tree` datatype implements trees with leaves (no value), small nodes (one value, two children) and large nodes (two values, three children):

(define-type Tree [leaf] [small-node (val number?) (left-child Tree?) (right-child Tree?)] [large-node (left-val number?) (right-val number?) (left-child Tree?) (center-child Tree?) (right-child Tree?)])

Every problem must come with an appropriate set of test cases. At a minimum the test cases must cover every branch in each function you write.

Implement a `count` function that takes a tree and returns the number of values in the tree.

Example:

(test (count (small-node 5 (leaf) (large-node 6 7 (leaf) (leaf) (leaf)))) 3)

Our trees must obey the following invariant:

the values in the left child of a small node must all be less than or equal to its value,

the values in the right child of a small node must all be greater than its value,

the values in the left child of a large node must all be less than or equal to its left value,

the values in the middle child of a large node must all be greater than its left value, but less than or equal to its right value,

and the values in the right child of a large node must all be greater than its right value.

Impement the function `obeys?`, which takes a tree and returns the boolean `#t` if it obeys the invariant, and the boolean `#f` otherwise. Your function must run in time proportional to the size of the tree, which rules out explicitly sorting a list of all the values in the tree.

From this point on, you should assume that all trees your functions receive obey this invariant, and all trees your functions produce must also obey it.

Implement the function `smallest`, which takes a tree, and returns the smallest number in the tree, or the string `"there is no smallest number in an empty tree"` if the tree is a leaf.

Your function should rely on the invariant to avoid exhaustively searching the tree.

Example:

(test (smallest (small-node 5 (leaf) (large-node 6 7 (leaf) (leaf) (leaf)))) 5)

Implement the function `in-order`, which takes a tree and returns the list of values in the tree, in order. The in-order traversal is defined as follows:

**small nodes:**left child, value, right child**large nodes:**left child, left value, center child, right value, right child

Example:

(test (in-order (large-node 1 3 (leaf) (small-node 2 (leaf) (leaf)) (leaf))) '(1 2 3))

Implement the function `contains?`, which takes a tree and a number, and returns `#t` if the number is found anywhere in the tree, `#f` otherwise.

Your function should rely on the invariant to avoid exhaustively searching the tree.

The second argument to the `contains?` function is “along for the ride”.

Example:

(test (contains? (small-node 5 (leaf) (leaf)) 6) #f)

Implement the function `large-nodes-begone` that takes a tree, and returns an identical tree with each large node replaced by an arrangement of small nodes.The resulting tree must, of course, contain all the same values as the original.

Implement the function `right-children-begone` that takes a tree, and returns a tree that contains the same values, but that uses only small nodes with only leaves as right children.

Click the handin button in DrRacket to hand in your submission before the deadline. Make sure you wait until you see the "Handin Successful." message before closing. Late homework will not be accepted.

Last update: Tuesday, January 3rd, 2017stamourv@eecs.northwestern.edu |