CSE 326, Spring 1995: Homework 2
Due 4/12/95
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.
 (10 points)
Assume we have two stacks where
the stack operations are Push1, Pop1, Top1, and Is_Empty1 for the first
stack and Push2, Pop2, Top2, and Is_Empty2 for the second stack.
Assume the stacks never overflow.

Show how to implement a queue using two stacks.
Design algorithms for Enqueue,
Dequeue, and Is_Empty for the queue using only the stack operations.

Are your algorithms efficient in the
sense that each queue operation takes constant time if each stack operation
takes constant time? Explain.

Are your algorithms efficient in the sense that starting with an empty
queue, n queue operations take O(n) time if each stack operations
takes constant time? Explain. (This part is difficult)
 (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 repesentation 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 sparse vector.