Department of Computer Science and Engineering CSE 130
University of California at San Diego Fall 1999

Team Project 2

DUE FRIDAY NOVEMBER 5, 1999, BEFORE 6 PM.

 



The purpose of this assignment is to apply some concepts of functional programming using the ML language, and to compare this experience with the experience of solving the same problem in C.  Your C program should be very similar to your ML program in its design and organization.

This project is to use a search algorithm called iterative deepening to solve a type of problem that sometimes appears on human intelligence tests: sequence prediction problems.  The aim in a sequence prediction problem is to predict the next member of a sequence of reals, assuming that the number in position n of the sequence is generated using some sequence function s(n), where the first element of the sequence corresponds to n = 0. For example, the function s(n) = 2n generates the sequence [1, 2, 4, 8, 16, ... ].

In this project, you will design and write a program capable of solving such prediction problems. The program will search the space of possible arithmetic expressions until it finds one that matches the observed sequence. The space of expressions that we will consider consists of all possible formulas built from the elements 1 and n, and the binary arithmetic operations +, x, -, /, and exponentiation. For example, the function 2n is written as (1 + 1)n in this language.

The iterative deepening algorithm will be explained in section and on a web page linked to this one.

You should use your program to find the sequence expressions for the sequences [1, 2, 3, 4, 5], [1, 2, 4, 8, 16], [0.5, 2, 4.5, 8], [0, 0, 0, 6, 24, 60], and [2, 0, 0, 2, 6, 12].
 

WHAT TO SUBMIT BY COMPUTER

You should create two files: idsearch.ml and idsearch.c, containing the programs. Make sure that if the solution is at depth d
then each program only uses O(d) space.  In other words, your programs must have no memory leaks.

Program idsearch.ml must contain a function solve that receives a list of reals as input, and outputs the next two numbers in the sequence:

val solve = fn : real list -> real list
Program idsearch.c must receive as input arguments the sequence, and as a result, print the next two numbers in the sequence. For example, the sequence [1, 2, 3, 4] is the input, and the output should be 5 6, when you run the program:
%> idsearch 1 2 3 4
To turn in your work, you will use a script called bundle. Simply cd to the directory containing all two source files and type the Unix command bundle P2. The bundle script knows which files to look for and submit. Remember to check the class web page at www-cse.ucsd.edu/classes/fa99/cse130/ for any changes to these directions.
 

WHAT TO SUBMIT ON PAPER

You should describe all your work in a well-written report of length at most ten pages.  Follow the same requirements as for the first assignment with regard to the paper. References that you may use are web pages and books. One recommended book is Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig.

The report should discuss what the important benefits and disadvantages are of ML in comparison with C, as illustrated by this programming project.  Some ML language features that you should consider:

As an appendix to your report, you should submit a printout of your software, with comments and documentation of professional quality. This documentation should be sufficient for another software engineer to maintain each program. Remember that good documentation is necessary but not sufficient. You should attach transcripts of test runs that show both your programs working correctly on the five test sequences given above.

Be sure to follow all the rules and guidelines explained in the CSE 130 course description.  Complete academic honesty is required.