Sparse arrays and matrices

In many application we require arrays which are very sparse, meaning that a large percentage of their space is taken up by useless information, usually zeroes. As you can imagine, in cases where only a small percentage of an array actually contains any information, it becomes a waste of space to use standard arrays so it makes sense to use more specialized data structures.

A. 1-d arrays

Depending on the data, there can be many kinds of sparse 1-dimensional arrays. For this exercise consider arrays of this form:

In other words, the array consists of a string of zeroes, then some data, and then a string of zeroes.

1. It dynamically allocates enough space to hold the useful data of a sparse array only. The parameters you are given are the size of the array, the number of useful entries and the position where the entries start. You must perform some sanity checking on these parameters before attempting to create the array.
2. Create two constructors and a destructor. The first constructor should take the array parameters as input only and initialize all of the array to 0. The second constructor should additionally take as input an array of ints copy its values to the useful part of the array you are making.
3. It allows the user random read access to any entry of the array. If the user attempts to read outside the useful region, your data structure should return a 0.
4. It allows the user random write access to the useful region only. In case the user tries to write something in the part of the array that is supposed to be 0, print an error message.
5. Overload the << and [] operators to work with your class.

• A well-commented or easy to understand header file called sparse_array_1d.h documenting the interface to your sparse array data structure.
• An implementation file called sparse_array_1d.cpp
• A short demo program called usearray1d.cpp showing an example of using the basic features of the class

B. 2-d arrays

What this means is that the upper right and lower left areas of the array are occupied by zeroes while the only real data resides in a thin ribbon going along the main diagonal of the matrix. Design and implement a data structure for such sparse 2-d arrays, following these specifications:

1. Create a constructor and a destructor. The constructor should take as input the size of the array (consider only square NxN arrays, so only one dimension is needed) and the thickness of the ribbon. To make this precise, if supplied with a thickness parameter t, you may assume that the element [0,t] (i.e. the (t+1)-th element of the first row) is where the useless area begins on the right. Similarly, the element [t,0] is where the useless area begins on the left. The border of the useless areas moves diagonally down and to the right, i.e. it consists of [1,t+1],[2,t+2],... and [t+1,1],[t+2,2],... The above example has thickness 3.
2. The space for the 2-d array should be dynamically allocated and must be large enough to fit the useful data only.
3. Create methods for random read and write access to the array as in the case of 1-d arrays.
4. Overload the [] and << operators, as in the case of 1-d arrays. Think carefully about what the [] operator should return and how it should work. Ideally we would like this to behave in a manner similar to standard 2-d arrays (i.e. accessing elements in the normal way, like x[5][6]).

• A well-documented or easy to understand header file called sparse_array_2d.h documenting the interface to your sparse array data structure.
• An implementation file called sparse_array_2d.cpp
• A short demo program called usearray2d.cpp showing an example of using the basic features of the class.
• It is possible to solve this problem either by building on the work you did for 1-d arrays, by starting from scratch, or by doing something in between. Submit a short paragraph in a text file called motivation.txt briefly explaining which route you selected and why you think this is the best idea.