Department of Computer Science and Engineering CSE 130
University of California at San Diego Spring 2002

Assignment 2 (Team Project) (Revised)

Deadline extended to Wednesday May 8 before the start of class.



The purpose of this project 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 assignment is a team project.  Each team must consist of exactly three students.  You have more than two weeks, but do start work immediately.

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 prediction problems like the one above. 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.  Here are some test cases: 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].  Here are additional notes on this project and general project notes.
 

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 space that is polynomial in d.  In other words, your programs must have no memory leaks.  Your program must be efficient enough to solve the test cases above.

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.0, 2.0, 3.0, 4.0] is the input, and the output should be 5.0 6.0, when you run the program:
%> idsearch 1.0 2.0 3.0 4.0
To turn in your work, you will use the turnin script as before. Remember to check the class web page 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 six pages, printed single-spaced and stapled.  Follow the same requirements as for the first assignment with regard to the paper.  You must staple a copy of the team self-evaluation form to your report.  This form is required for all team projects in 130.

References that you may use are web pages and books. Two recommended books are Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, and Elements of ML Programming, Second Edition Using ML97 by Jeffrey D. Ullman.

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:

In addition, your software must have comments and documentation of professional quality. This documentation should be sufficient for another software engineer to maintain each program.  Good documentation is necessary but not sufficient: your software must also be organized well and coded with good style.  Your programs in ML and C must be straightforward and easy to understand.  In particular, it must be easy to see that you have implemented the iterative deepening algorithm correctly.

This project will be graded as follows:

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