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.
  1. (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.
  2. (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 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.