CSE 326, Spring 1997: Homework 2
Due 4/16/97
For each problem below you will be asked to design an algorithm. In
addition to giving the pseudocode for the algorithm, give an explanation
of why the algorithm works.
 (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 nonzero 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 nonzero 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.

(10 points)
Find the order of magnitude for each of the following recurrences:
 T(n) <= 3T(n/2) + cn, T(1) <= b
 T(n) <= T(n/2) + cn, T(1) <= b
You can assume that n is a power of two in your derivations.

(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.
You can assume you have already defined a
split
function
that returns a duo
with half the list in the
field and the other half in the second
field.
 First, carefully define
merge
which takes two sorted
lists as arguments and returns a sorted list.
 Second, 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.
Try to make your pseudocode as simple and elegant as possible.