Data Structures

Matrices are fundamental data structures in computer science that are used in everything from weather simulations to schedulers. In Scheme, a 2-dimensional n by m matrix may be represented as a vector V of size n, where each element of V is itself a vector of size m.

For example, the matrix:

is a 4 by 3 matrix which might be represented by a vector V as follows:

In many simulations, matrices just happen to have many elements that are always 0 (zero). This subclass of matrices is said to be sparse because the interesting elements are sparsely distributed across the matrix. For example, the 4 by 4 identity matrix is a sparse matrix:

Sparse matrices may be represented more efficiently than regular matrices if the number of non-zero elements in the matrix is very small. For very large matrices, like the ones used in weather simulations, this space saving can literally save us from having to use gigabytes of memory.

1. Describe in words a data structure that you would use to represent sparse matrices and draw a picture of the data structure you would use to represent the 4 by 4 identity matrix (shown above). Your data structure should provide support for determining the number of rows and columns in the matrix, as well as support for extracting elements from the matrix when given a row and column.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
2. The sum of two n by m matrices A and B is the n by m matrix C where the element c_i,j = a_i,j + b_i,j. For instance:

   

   Write a Scheme function sparse-add which takes to sparse matrices A and B and produces a new sparse matrix that is the sum of A and B. Write neatly and use comments in your code to explain what you're doing.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

Solution

Return to CS 212 Prelim 2 - Spring 1998