Recall, operations over sparse matrices require methods that skip over the zero-
ID: 3904003 • Letter: R
Question
Recall, operations over sparse matrices require methods that skip over the zero-elements. The enclosed class file provides a design where th e O(1) non-zero elements in each row of the matrix is stored in an unordered linked list. Add the missing code for the methods in the class that allow the Main routine to operate correctly.
------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------
Explanation / Answer
//SparseMatrix.java
package com.src;
public class SparseMatrix {
public static final int MAX = 1000;
public SparseMatrix(int size) {
n = size;
for (int i = 1; i <= n; i++)
rowStart[i] = null;
}
public int getSize() {
return n;
}
public double getVal(int i, int j) {
boolean found = false;
MatrixElement current = rowStart[i];
while (current != null && !found) {
if (current.col == j)
found = true;
else
current = current.next;
}
if (found)
return current.value;
else
return 0;
}
public int assign(int i, int j, double val) {
if (i > n || j > n)
return -1;
else {
boolean found = false;
MatrixElement current = rowStart[i];
while (current != null && !found) {
if (current.col == j)
found = true;
else
current = current.next;
}
if (found) {
current.value = val;
return 0;
} else {
MatrixElement newElement = new MatrixElement(i, j, val);
newElement.next = rowStart[i];
rowStart[i] = newElement;
return 0;
}
}
}
public int increaseBy(int i, int j, double val) {
// ADD CODE HERE
if (i > n || j > n)
return -1;
else {
boolean found = false;
MatrixElement current = rowStart[i];
while (current != null && !found) {
if (current.col == j)
found = true;
else
current = current.next;
}
if (found) {
current.value += val;
return 0;
}
}
return -1;
}
public SparseMatrix add(SparseMatrix other) {
// ADD CODE HERE
if (other.getSize() != n)
return null;
else {
SparseMatrix result = new SparseMatrix(n);
for (int i = 1; i <= n; i++) {
MatrixElement e1 = this.rowStart[i];
while (e1 != null) {
MatrixElement e2 = other.rowStart[e1.col];
while (e2 != null) {
result.increaseBy(i, e2.col, this.getVal(i, e1.col) + other.getVal(e2.row, e2.col));
e2 = e2.next;
}
e1 = e1.next;
}
}
return result;
}
}
public SparseMatrix mult(SparseMatrix other) {
if (other.getSize() != n)
return null;
else {
SparseMatrix result = new SparseMatrix(n);
for (int i = 1; i <= n; i++) {
MatrixElement e1 = this.rowStart[i];
while (e1 != null) {
MatrixElement e2 = other.rowStart[e1.col];
while (e2 != null) {
result.increaseBy(i, e2.col, this.getVal(i, e1.col) * other.getVal(e2.row, e2.col));
e2 = e2.next;
}
e1 = e1.next;
}
}
return result;
}
}
public SparseMatrix copy() {
SparseMatrix result = new SparseMatrix(n);
for (int i = 1; i <= n; i++) {
MatrixElement e = rowStart[i];
while (e != null) {
result.assign(i, e.col, e.value);
e = e.next;
}
}
return result;
}
public SparseMatrix transpose() {
// ADD CODE HERE
if (this.getSize() != n)
return null;
else {
SparseMatrix result = new SparseMatrix(n);
for (int i = 1; i <= n; i++) {
int j=1;
MatrixElement e1 = this.rowStart[i];
while (e1 != null) {
result.assign(j++, i, e1.value);
e1 = e1.next;
}
}
return result;
}
}
public SparseMatrix negative() {
// ADD CODE HERE
if (this.getSize() != n)
return null;
else {
SparseMatrix result = new SparseMatrix(n);
for (int i = 1; i <= n; i++) {
int j=1;
MatrixElement e1 = this.rowStart[i];
while (e1 != null) {
result.assign(i, j++, -1*e1.value);
e1 = e1.next;
}
}
return result;
}
}
private int n;
private MatrixElement[] rowStart = new MatrixElement[MAX];
}
//MatrixElement.java
package com.src;
public class MatrixElement {
public MatrixElement(int i, int j, double val) {
// TODO Auto-generated constructor stub
this.row = i;
this.col = j;
this.value = val;
this.next = null;
}
public MatrixElement next;
public int col;
public int row;
public double value;
}
//MatrixMain.java
package com.src;
public class MatrixMain {
public static void main(String[] args) {
SparseMatrix M1 = new SparseMatrix(4);
SparseMatrix M2 = new SparseMatrix(4);
M1.assign(1, 2, 12);
M1.assign(3, 2, 32);
M1.assign(2, 2, 22);
M1.assign(1, 1, 11);
M1.assign(4, 4, 44);
M1.assign(3, 1, 31);
M1.assign(2, 3, 23);
M1.assign(4, 2, 42);
M2.assign(1, 2, 12);
M2.assign(1, 3, 13);
M2.assign(1, 4, 14);
M2.assign(2, 2, 22);
M2.assign(2, 4, 24);
M2.assign(3, 1, 31);
M2.assign(3, 3, 33);
M2.assign(4, 4, 44);
SparseMatrix M3=null;
for(int i=1;i<=4;i++) {
System.out.println();
for(int j=1;j<=4;j++)
System.out.print(M1.getVal(i, j) + " ");
}
System.out.println();
for(int i=1;i<=4;i++) {
System.out.println();
for(int j=1;j<=4;j++)
System.out.print(M2.getVal(i, j) + " ");
}
System.out.println();
M3=M1.add(M2);
for(int i=1;i<=4;i++) {
System.out.println();
for(int j=1;j<=4;j++)
System.out.print(M3.getVal(i, j) + " ");
}
System.out.println();
M3 = M1.mult(M2);
for(int i=1;i<=4;i++) {
System.out.println();
for(int j=1;j<=4;j++)
System.out.print(M3.getVal(i, j) + " ");
}
System.out.println();
M3 = M1.transpose();
for(int i=1;i<=4;i++) {
System.out.println();
for(int j=1;j<=4;j++)
System.out.print(M3.getVal(i, j) + " ");
}
System.out.println();
M3 = M1.add(M2.negative());
for(int i=1;i<=4;i++) {
System.out.println();
for(int j=1;j<=4;j++)
System.out.print(M3.getVal(i, j) + " ");
}
System.out.println();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.