Data Structure HomeworkLLMainClass.java

-----------------------------------------------------

LLSparseVec.java

-----------------------------------------------------

public class LLSparseVec implements SparseVec {

public LLSparseVec(int len){ return; }

@Override public int getLength() { // TODO Auto-generated method stub return 0; }

@Override public int numElements() { // TODO Auto-generated method stub return 0; }

@Override public int getElement(int idx) { // TODO Auto-generated method stub return 0; }

@Override public void clearElement(int idx) { // TODO Auto-generated method stub

}

@Override public void setElement(int idx, int val) { // TODO Auto-generated method stub

}

@Override public int[] getAllIndices() { // TODO Auto-generated method stub return null; }

@Override public int[] getAllValues() { // TODO Auto-generated method stub return null; }

@Override public SparseVec addition(SparseVec otherV) { // TODO Auto-generated method stub return null; }

@Override public SparseVec subtraction(SparseVec otherV) { // TODO Auto-generated method stub return null; }

@Override public SparseVec multiplication(SparseVec otherV) { // TODO Auto-generated method stub return null; }

}

SparseVec.java

-------------------------------------------------

public interface SparseVec { // problem 1 int getLength(); //return the length of the vector int numElements(); //return total number of nonzero elements in the vector int getElement(int idx); //return the element at a given idx void clearElement(int idx); //set the element at idx to zero void setElement(int idx, int val); //set the element at idx to val // get all nonzero indices int[] getAllIndices(); // get all nonzero values int[] getAllValues(); SparseVec addition(SparseVec otherV); // this vector + otherV // return a new vector storing the result SparseVec subtraction(SparseVec otherV); // this vector - otherV // return a new vector storing the result SparseVec multiplication(SparseVec otherV); // this matrix .* otherV // return a new vector storing the result }

LLSparseM.java

----------------------------------------------------------

public class LLSparseM implements SparseM {

public LLSparseM(int nr, int nc){ return; }

@Override public int nrows() { // TODO Auto-generated method stub return 0; }

@Override public int ncols() { // TODO Auto-generated method stub return 0; }

@Override public int numElements() { // TODO Auto-generated method stub return 0; }

@Override public int getElement(int ridx, int cidx) { // TODO Auto-generated method stub return 0; }

@Override public void clearElement(int ridx, int cidx) { // TODO Auto-generated method stub

}

@Override public void setElement(int ridx, int cidx, int val) { // TODO Auto-generated method stub

}

@Override public int[] getRowIndices() { // TODO Auto-generated method stub return null; }

@Override public int[] getOneRowColIndices(int ridx) { // TODO Auto-generated method stub return null; }

@Override public int[] getOneRowValues(int ridx) { // TODO Auto-generated method stub return null; }

@Override public SparseM addition(SparseM otherM) { // TODO Auto-generated method stub return null; }

@Override public SparseM subtraction(SparseM otherM) { // TODO Auto-generated method stub return null; }

@Override public SparseM multiplication(SparseM otherM) { // TODO Auto-generated method stub return null; }

}

SparseM.java

---------------------------------------------------

public interface SparseM { // problem 2 int nrows(); //return number of rows int ncols(); //return number of columns int numElements(); //return total number of nonzero elements in the matrix int getElement(int ridx, int cidx); //return the element at a given entry (ridx, cidx), void clearElement(int ridx, int cidx); //set the element at (ridx,cidx) to zero void setElement(int ridx, int cidx, int val); //set the element at (ridx,cidx) to val // get indices of non-empty rows, sorted int[] getRowIndices(); // get indices of non-empty cols, sorted int[] getOneRowColIndices(int ridx); // get values of a given row int[] getOneRowValues(int ridx);

// methods for problem 3 SparseM addition(SparseM otherM); // this matrix + otherM // return a new matrix storing the result SparseM subtraction(SparseM otherM); // this matrix - otherM // return a new matrix storing the result SparseM multiplication(SparseM otherM); // this matrix .* with otherM // return a new matrix storing the result }

Problem 1: Sparse Vector Using Linked List (5 pts) Implement the linked list sparse vector class in LLSparse Vec.java so that LLMain Class can be executed. The command line arguments are VEC/MAT Filel A/S/M File2 ... Nodes in the linked list are nonzero elements of the vector, sorted according to their indices. The length of a vector is specified at construction. When an element is set to zero, the corresponding node should be removed. Implement the constructor, accessor methods, getElement, setElement, clearElement, getAllIndices, getAllValues. Implement addition, subtraction and element-wise multiplication methods in LLSparse Vec. The method subtraction(otherV) means the current vector minus other V. The algorithm has to be 0(m), in which m is the maximum number of nonzero elements in a vector (length of the list). Only algorithms with O(m) complexity will get credits. All operations return a new sparse vector object, storing the result. If the two vectors' length do not match, return a null object. When LLMainClass is called using VEC argument and with at least one input file, the program should be able to run correctly and give the same output as ArrayMainClass, else a proper error message should be generated. Examples: idx = 6 32EE. idx = 4 val = -2 val = 7 val = 9 idx = 9 val = 3 idx = 4 val = 2 idx = 7 val = -7 idx = 9 val = 2 idx = 3 val = 7 idx = 6 val = 9 idx = 7 val = -7 idx = 9 val = 5 Page 1 of 5 idx = 4 val = -2 idx = 6 val = 9 idx = 9 val = 3 idx = 4 val = 2 idx = 7 val = -7 idx = 9 val = 2 idx = 9 idx = 4 val = -4 val = 6 Problem 2: Sparse Matrix Using Linked List (5 pts) Implement the linked list sparse matrix class in LLSparseMat.java so that LLMainClass can be executed with MAT argument. The command line arguments are VEC/MAT Filel A/S/M File2 ... RowHead nodes correspond to nonzero rows. Each rowhead node stores a LLSparse Vec, storing a nonzero row. It also has a pointer to the next rowhead. When a row becomes empty (no nonzero elements), the rowhead should be removed. Implement the constructor, accessor methods: getElement, setElement, clearElement, numElements (returns number of non-zero elements). getRowIndices returns an array of indices of rows with nonzero elements. getOneRowCollndices returns an array of nonzero column indices of the row. Use LLSparse Vec.getAllIndices(). getOneRow Values returns an array of nonzero values. Use LLSparse Vec.getAllValues(). NOTE that these methods should all be linear to the number of nonzero rows or nonzero elements. Page 2 of 5 When LLMainClass is called using MAT argument and with at least one input file, the program should be able to run correctly and give the same output as Array MainClass, else a proper error message should be generated. First Row 20 x 30 nElements = 7 ridx = 5 idx = 7 val = -1 idx = 11 val = 99 idx = 21 val = 11 ridx = 9 idx = 3 val = 2 idx = 11 val = -10 ridx = 19 idx = 7 val = -2 idx = 21 val = 12 Problem 3: Sparse Matrix Operation Linked List (5 points) Implement the addition, subtraction and multiplication methods in LLSparseM. The algorithm has to be O(m), in which m is the maximum number of nonzero elements in a matrix. Only algorithms with O(m) complexity will get credits. All operations return a new sparse matrix object, storing the result. The method subtraction(otherM) means the current vector minus otherM. If the two matrices' dimensions (nrows, ncols) do not match, return a null object and output a proper error message. When LLMainClass is called using MAT argument and with at least one input files, the program should be able to run correctly and give the same output as ArrayMainClass, else a proper error message should be generated. Problem 4: Performance Evaluation (5 bonus points) Write a report on matrix construction and operation time, comparing Array and LL implementation: 2 plots, on construction, and on operations. Each plot has two curves: Array Page 3 of 5 import java.util.Scanner; import java.io.File; public class LLMainClass { public static SparseM ParseMatrix(String file_name) { Scanner sc = null; String tmps; SparseM M = null; try { SC = new Scanner(new File(file_name)); while (sc. hasNext()) { tmps = ss.next(); if(tmps.equals("MATRIX")) { // initialize the matrix int nr = sc.nextInt(); int nc = Sc.nextInto; M = new LLSparseM(nr.nc); }else if(tmps.equals("END")) { // finished, return the matrix SS..close(); return M; }else if(tmps.equals("SET")) { 11 set an element int ridx = sc.nextInt(); // row index int cidx = 56.nextInt(); // col index int val = sc.nextInt(); // value M.setElement(ridx, cidx, val); }else if(tmps.equals("CLEAR")){ // clear an element int ridx = sc.nextInt(); // row index int cidx = sc.nextInt(); // col index M.clearElement(ridx, cidx); SS.close(); return M; } catch (Exception e) { return nu; } public static Sparsevec ParseVector(String file_name) { Scanner ss = null; String tmps; Sparseves V = null; try { SC = new Scanner(new File(file_name)); while (sc. hasNext()) { tmps = sc.next(); if(tmps.equals("VECTOR")) { // initialize the matrix int len = sc.nextInt(); V = new LLSparsevec(len); }else if(tmps.equals("END")) { // finished, return the matrix SS.close(); return V; }else if(tmps.equals("SET")) { 1/ set an element int idx = sc.nextInt(); // index int val = sc.nextInt(); // value V.setElement(idx, val); }else if(tmps.equals("CLEAR")) { // clear an element int idx = sc.nextInt(); // index V.clearElement(idx); SS..close(); return V; } catch (Exception e) { return null; public static void main(String[] args) { try{ int n = args.length; if(n