CS-UH 1050 Data Structures - Assignment 1: Matrix Computation
Assignment 1 - Matrix Computation
1 Code of Conduct
2 Introduction
In this assignment, you will develop a matrix computation system using C++ that will be used to perform addition and multiplication on matrices. A matrix can be sparse, i.e., some elements are zeros. For memory space efficiency, you can store such matrix in M+N+V space, instead of M*N, where M is the number of rows, N is the number of columns, and V the number of non-zero elements in the matrix.
You are supposed to create a program utilizing mainly the following covered topics and concepts:
● File input/output in C++ ● Object Oriented Programming ● Arrays and Linked Lists Note: You are not allowed to use any built-in STL data structures such as List, Vector, etc.
3 Implementation
You will be provided with a starter code containing class declarations and the main function. Your task is to complete the definition and implement all the missing methods of the class. You may add new helper methods in the class, but you are not allowed to change/remove the headers of existing methods. The input/output format of the program should be the same as illustrated in the provided screenshots.
A matrix can be stored as Linked Lists as demonstrated in the following example. Each Node of a linked list represents a non-zero member of the matrix and contains the row index, column index, data value, and pointers to the next and down cells, if any. For example, the matrix [[0,0,1,0,0], [0,0,0,0,0], [0,1,0,0,1],[0,0,0,1,0, [0,0,0,0,0]] can be stored as 2 Arrays of Linked Lists as shown below:
The first non-zero element is at (0, 2). It is pointed to by the header element of row 0. The next non-zero element is at (2, 1), which has a pointer to (2,4). Each non-zero element is pointed to by the header element for the corresponding columns. This way, the actual size of this matrix as built and stored in memory is 5+5+4= 14 instead of 5*5=25!
And as a result, a node of a non-zero element/value may be defined as follows:
Class Node {
Public:
int row;
int column;
int value;
Node* next; //pointer to the next node within the same row
Node* down; //pointer to the next node within the same column
}Method Description:
When your program starts, the user is presented with the list of possible commands. The user is able to interact with the system using the commands until an exit command is issued.
The following features are required to be implemented in the matrix computation system:
void LinkedMatrix::create(int numRows, int numCols) This method builds an empty matrix of size numRows*numCols based on the optimized matrix data structure. int LinkedMatrix::getNumRows() This method returns the number of rows. int LinkedMatrix::getNumCols() This method returns the number of columns. void LinkedMatrix::insertElement(int Row_Indx, int Col_Indx, int value) This method inserts an element/node with a value, which is not equal to zero, to the matrix at (Row_Indx, Col_Indx). If an element/node already exists at (Row_Indx, Col_Indx), its value is to be updated with the value given as an argument. void LinkedMatrix::removeElement(int Row_Indx, int Col_Indx) This method removes the element/node at (Row_Indx, Col_Indx). void MatComp::importMatrix(LinkedMatrix& newMat, string filename) This method reads a matrix from the given file into the provided LinkedMatrix object, which follows the optimized representation of a matrix described in the previous section.
void MatComp::multi(LinkedMatrix& Mat, int a) This method multiplies Matrix “Mat” by the constant ‘a’. The result is stored in “Mat”. In other words, this method updates the matrix provided via the first argument.
void MatComp::add(LinkedMatrix& Mat1, LinkedMatrix& Mat2) This method adds the matrices Mat1 and Mat2, which are of the same size. The result is stored in “Mat1”. In other words, this method updates the matrix provided via the first argument.
void MatComp::multi(LinkedMatrix& Mat1, LinkedMatrix& Mat2, LinkedMatrix& Mat3) This method multiplies the matrices Mat1 (of size ab) and Mat2 (of size bc) together. That means the number of columns in Mat1 should be equal to the number of rows in Mat2. The resulting matrix is stored in “Mat3”, which would be of size a*c, then displayed along with its assigned ID. If a provided matrix ID does not exist, a message should be displayed saying “No matrix with this ID exists in the system!”.
void MatComp::exportMat(LinkedMatrix& Mat, string filename) This method writes the matrix “Mat” to a new file.
void MatComp::display(LinkedMatrix& Mat) This method displays the provided matrix “Mat”. If the provided matrix ID does not exist, a message should be displayed saying “No matrix with this ID exists in the system!”.
Matrix File Format:
A matrix file (.txt), which you can read/import or generate/export, will contain the original dimensions of the matrix (i.e., the number of rows and the number of columns), the number of non-zero elements, and a list of these elements with their addresses. The following is an example of the contents of such a file:
Constraints:
-
The list of elements in a matrix file must be ordered by column first, and then by row as illustrated in the file example.
-
If a non-zero member becomes zero as a result of an operation, it should be removed from the matrix.
-
The matrices should be given IDs based on the order of import and/or generation via multi-by-matrix command. For example, if you import a matrix, import another and then multiply the first one by the second, a third matrix is generated and stored next in the system. Therefore, the ID of the firstly imported matrix is ‘A’, the ID of the secondly imported matrix is ‘B’, and the ID of the generated matrix from multiplication by matrix is ‘C’. If you were to import one more matrix, it would have had ‘D’ as an ID.
-
You need to check the validity of ANY input provided by the user and handle errors.
-
user should be given up to 3 chances to provide a valid value as an input. In case a user uses the 3 chances without success, then the operation will time-out and the user is back to the main program, where they can enter a command.
You need to make sure that the conditions of any operation are met for it to be executed successfully.
4 Grading
Quality in Code Organization & Modularity
- Defining ALL the needed classes correctly, with their sets of attributes and methods (including the constructors and destructors), and creating objects from each class properly
- Proper initiation and termination of the system Methods to design and implement with correct execution: import (1.5 pts), export (1.5 pts), add (1.5 pts), multi-by-const (1.5 pts), multi-by-matrix (1.5 pts), display (1.5 pts), create (1 pt), getNumRows (1 pt), getNumCols (1 pt), insertElement (1.5 pts), removeElement (1.5 pts) Proper error handling of missing and invalid input, etc. Properly commenting the code (i.e., code documentation)
