Home  |   Notes  |   Languages  |   Programs  |   Homework
Program Assignment 4

75 Points
Due: Wednesday, 11/29/00 at 5:00PM

 Problem: Rooted Trees in SML

In this programming assignment, you will implement a data type for rooted trees in SML, as well as some associated functions. Recall that, mathematically, a rooted tree T is a directed graph, with a distinguished node r, such that every node in T is reachable from the root by a unique path. You are to define an SML data type rooted_tree to represent a rooted tree. In addition to representing a rooted tree, the rooted_tree data type must be a parameterized type in which every node in the tree must have a label 'a of the same type. If a node in a rooted tree has 2 or more children, then its children must have a fixed order from left-to-right. You are also to implement the following SML functions:

 Implementation Language

For this assignment, your program must be written in SML.

Your solution will consist of a file of SML datatype and function definitions.

If your program is in the file bob.sml, then you can load it at the SML prompt as follows:

- use "bob.sml";

SML comments are enclosed by (* and *).

 Input and Output Formats

As your SML program will be tested with the SML interpreter, you do not specifically have to be concerned with an input or output format; the interpreter takes care of that.

 Testing Your Program

Before submitting your SML program file, you must test it thoroughly. To do this, you should devise a set of tests of your own that you believe exhaustively test your SML program.

Here is a small set of tests that you may start with, and here are the results for the function calls, starting with member_of(tree5,5). Please be certain that your SML program passes at least the above tests before submitting it.

 Submitting Your Program

Your SML program must be in a single file named <pid>.sml, where <pid> must be replaced by your Virginia Tech PID. That file and any auxiliary files, such as test results, must be packaged as a zip file (or tar file) named <pid>_project4.zip, which is attached to email sent to the class account, cs3304@courses.cs.vt.edu. The subject of the mail must be "Program assignment 4" - without quotes.

For example, the GTA's submission will be a SML file: derao.sml along with the input file containing the test cases and their output, packaged in a zip file: derao_project4.zip. Further, derao_project4.zip will be mailed to cs3304@courses.cs.vt.edu with subject Program assignment 4.

Your SML implementation is to be organized in a single file. The comments at the beginning of the file should identify the assignment and should give your name. Every SML predicate should be preceded by comments explaining its purpose and implementation.

Be sure to follow the Program Submission Guidelines in preparing your report to turn in. In accordance with these guidelines, you will need to develop a set of test cases for your program that tests both positive and negative cases. For test cases that you are unable to run, be sure to indicate "Unable to perform test" in the corresponding test result within your report.

NOTE: Failure to follow the submission guidelines may result in a grade penalty.

Home  |   Notes  |   Languages  |   Programs  |   Homework

copyright © 2000 Virginia Tech, ALL RIGHTS RESERVED
Last modified: October 29, 2000, 05:31:20 EST, by Lenwood S. Heath <heath@cs.vt.edu>