CSE 326, Spring 1998: Homework 2

Due 4/10/97

1. (20 points) A sparse matrix is one where a high percentage of the entries are zero. An nxn sparse matrix can be represented efficiently in an adjaceny list like structure, called the "sparse matrix representation". The sparse matrix representation consists of an array R[1..n] of pointers where R[i] points to an list of nodes corresponding to non-zero entries of in row i of the matrix. Each node of the data structure has three fields ["column", "value", "next"]. The node [j,v,p] is on R[i]'s list if the matrix has value v in position [i,j]. There is no entry of the form [j,v,p] on R[i]'s list if the matrix has value 0 in position [i,j]. The nodes in R[i]'s list are sorted by column number in increasing order.
   • Design an algorithm to multiply a sparse matrix times a vector, where the vector is represented as an array V[1..n].
   • Design an algorithm to multiply a sparse matrix times a vector, where the vector is represented as "sparse vector," that is, a list of nodes of the non-zero entries of the vector V[1..n].
   • Design an algorithm to transpose a sparse matrix. If M is a matrix, then its transpose is defined as M^T where M^T[i,j] = M[j,i]. The result of your algorithm is also a sparse matrix. Your algorithm can be destructive.
   • Design an algorithm to multiply two matrices both in sparse matrix representation form. The result is a matrix in sparse representation. Hint: In order to multiply two matrices, one of them should be transposed to make the process easier.
2. (10 points) In this problem you should carefully design and analyze a list oriented recursive mergesort algorithm. Assume the input data is found in an unsorted linked list. Mergesort should return (destructively) a sorted list. Mergesort first splits the list into two approximately equal length lists, recursively mergesorts the two lists, then merges the two sorted lists into a final sorted list.
   First, define the function split that takes a list as input and returns two lists of equal or almost equal size, where the union of the two lists is the original list. For example, if the original list is a0, a1, a2, a3, ... then the returned lists can be a0, a2, ... and a1, a3, ... To return two list a new type of node can be used to hold them. Perhaps a good name for the new typ is duo.
   • Second, carefully define merge which takes two sorted lists as arguments and returns a sorted list.
   • Third, define mergesort which takes an unsorted list and returns a sorted list.
   • Write a recurrence describing the running time of the algorithm and solve it carefully.