EECS 321 Programming Languages: Homework 1

Part 0 – Set up DrRacket & Create Handin Account

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 > character) and the number 1267650600228229401496703205376.

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

http://www.eecs.northwestern.edu/~stamourv/teaching/321-W17/cs321.zip
 
Then press Install. Wait for the Close button to become enabled (and then click it). Restart DrRacket.

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.

Part 1 – Honor Code

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.

Part 2 – Trees

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)

Part 3 – Invariant

Our trees must obey the following invariant:

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

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

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

  4. 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,

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

Part 4 – Smallest

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)

Part 5 – In-Order Traversal

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:

  1. small nodes: left child, value, right child

  2. 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))

Part 6 – Contains?

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)

Part 7 – Getting Rid of Large Nodes

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.

Part 8 – Getting Rid of Right Children

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.

Part 9 – Handin

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, 2017
stamourv@eecs.northwestern.edu