95-706 Spring 2000

Due Date/Time: Wednesday, February 16, 2000 at 11:00 AM

1. Introduction

An essential part of the background required to understand and apply the major ideas from object oriented analysis and design is being involved in the creation of a program that is too large for one person to understand completely at any time.

The purpose of this object oriented design and implementation project is to provide students who come to this course with a limited exposure to programming to encounter a program that is conspicuously larger than any of their prior programs. Students who have been exposed to larger programming projects should find this project a good way to review some of the data structures work that they have done in the past.

A sparse matrix is a matrix with the property that almost all of its elements are zero. Such matrices are frequently used in branches of theoretical physics and in business and economics related situations. The computations that are performed on such matrices can be done by many contemporary computers but the storage requirements for large matrices can overwhelm the storage systems of most or all computers.

A simple mental model of a sparse matrix is of a matrix that has 1000 rows and 1000 columns, i.e., a million matrix elements, with at most 200 non-zero entries. This means that it is possible to achieve significant storage savings by using a non-standard representation of the matrices. In actual applications, the sizes are 10 to 1000 times larger so the storage savings can be the difference between a tractable problem and an intractable problem.

2. General Specifications

An object oriented program to read, write, delete, add, subtract and multiply sparse matrices is to be written using an object oriented programming language. The detailed functional specifications appear in the next section.

Java, C++ and Smalltalk are acceptable object oriented languages. If you want to use a different language, please consult with the instructor before you start. Languages like C and Basic are not acceptable.

Suggestions for designing the program will be offered in class on Wednesday, January 19, 2000. You are not required to follow the design suggestions.

All of the important classes will first be declared in a structure like a Java Interface or C++ Pure Virtual Class.

All error reporting and handling will be done using exceptions. Return codes are not permitted.

You may use the standard libraries provided with your programming language. However, you may not use classes that handle data structures such as linear lists, hash tables, etc.

All input is to be read from standard input and all output is to be written to standard output, including error messages. All input is to be echoed to the output but reformatting of sparse matrix input is permitted.

3. Functional Specifications

At the highest level, the program that you will be writing is to read a line of input and then write that line of input followed by the appropriate output, correct data or error messages.

Because of this very straightforward high level specification, the functional properties of the program are best specified by making statements about the response to specific inputs. The remainder of this section is that description.

A logical line of input may appear on one or more physical lines of input. Each logical line begins in column 1 of the first line and is terminated by the character semi-colon (;). Note that this implies that a semi-colon is the last non blank character on the last physical line of a logical line of input.

The process of input line reading is a necessary evil for running and testing your program and, therefore, the input processor will be as simple as possible. Syntactically incorrect input lines must be rejected but don't go through elaborate steps to find obscure errors. Elaborate error checking is beyond the scope of this project.

Matrix names consist of exactly one upper-case letter from ISO Latin-1.

Your program is to read a sequence of logical lines and process the five different lines that may appear as follows:

(1) Matrix Input

The program accepts sparse matrices as input in the following format:

A : n m e[1] e[2] ... e[k];

where "A" is the matrix name, "n" and "m" are positive integers (the number of rows and columns, respectively, in matrix A) and the e[j] are the non-zero elements of A and are of the form (i j A[i, j]). Here, i and j are positive integers such that

1 <= i <= n and 1 <= j <= m.

A[i,j] is an integer, positive, negative or zero.

The specification of the values of the elements of a matrix form a logical line terminated by a semi-colon. A logical line my extend over more than one physical line. You may assume that the matrix name appears in column 1 and the character colon (:) appears in column 3. A single matrix element, e[i], will not be divided across physical line boundaries though there may be a number of spaces between a ) and a (.

Except as required above, white space may be ignored in inputs.

If there is no matrix with the given name in storage, then storage for the matrix is to be allocated and the values entered into the matrix. If a zero node appears in the input, you must not enter the node into your data.

(2) Deleting matrices

Upon reading a line which contains

DELETE A;

where "A" is a matrix name, the matrix A is to be deleted from storage. If the matrix is unknown, print an error message and continue processing. The input text will appear exactly as shown, beginning in column 1.

(3) Printing matrices

Upon reading a line which contains

PRINT A;

where "A" is a matrix name, the value of the matrix is printed in input format if the matrix is known. If the matrix is unknown, print an error message and continue processing. The input text will appear exactly as shown, beginning in column 1.

(4) Expression Evaluation

Upon reading a simple assignment statement of the form

C := A + B;

compute the sum of the matrices A and B and assign the resulting matrix as the value of C. If matrix C exists, the matrix is to be cleared of non-zero elements before the new value is assigned to C. Similar statements apply when the arithmetic operator is - (subtraction) and * (multiplication).

If one or both of A and B are not in storage print an error message and continue processing.

(5) Ending execution

Upon reading the line

$END

print the input line, the message "Execution terminated." and terminate execution.