Please
read the assignment
submission rules and the academic
dishonesty page before you start work on this assignment. Failure to
comply by these rules will cost a significant percentage of your assignment
grade.
Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial, if you have trouble with the classpath settings you could try reading this tutorial.
Unless
stated otherwise, you are not allowed to use any classes from the
dataStructures or the java.util packages.
For
any coding question below, even though you may not use any of the methods of
the class you are extending, you MAY use the constructor of the class to be
extended when you create the constructor of your new class. For example, you
may do something like this:
public ALLExtended (){
super();} public ALLExtended( int n ){
super(n);}
You may NOT
use any built-in array functions in the java API.
1) This exercise will require you to devise a simple calculator for polynomials with 2 variables. We use a 2D matrix to store the coefficients. And two operations add and sub will be supported.
For example, Let A(x,y)= (x^2)(y^2)-10x-5(y^3)+100 B(x,y)= (x^3)(y^2)-xy+1.
First, we get their coefficients matrixes,
|
100
0 0 -5 ma = -10 0
0 0
0 0 1 0 |
1
0 0 mb = 0 -1 0
0 0 0
0 0 1 |
where element [i,j] represents the coefficient of the term (x^i)(y^j) in the original polynomial.
Then, we calculate the coefficients matrix of C(x,y)=A(x,y)+B(x,y)
101
0 0 -5
mc = -10 -1
0 0
0 0 1 0
0 0 1 0
Therefore, the result should be
C(x,y) = (x^3)(y^2)+(x^2)(y^2)-xy-10x-5(y^3)+101
Note:
1: These are matrix add and subtract operations, *but* the matrices must first be "padded" with zeroes so they both have the same number of rows and columns. For instance, in the above example, the dimensions of ma and mb do not agree, but addition and subtraction still works.
2: Assume that coefficients are all integers;
3: The index of rows and the columns start from 0.
The template for the class is given below:
package dataStructures;
public class PolyIn2DArray {
int [][]coef_;
int xSize_;
int ySize_;
public PolyIn2DArray(int xSize,int ySize)
{
// May modify this part if needed.
if (xSize <= 0)
{
throw new IndexOutOfBoundsException("xSize <= 0");
}
if (ySize<0)
{
throw new IndexOutOfBoundsException("ySize <= 0");
}
xSize_ = xSize;
ySize_ = ySize;
coef_=new int[xSize_][ySize_];
}
// May write helper methods if needed.
public void add(PolyIn2DArray a,PolyIn2DArray b)
{
// Your code goes here
}
public void sub(PolyIn2DArray a,PolyIn2DArray b)
{
// Your code goes here
}
public void print()
{
String s = "";
boolean first = true;
for(int i
= xSize_ - 1 ; i >= 0 ; i--)
{
for(int j = ySize_ - 1 ; j >= 0 ; j--)
{
int coef
= coef_[i][j] ;
if(coef == 0)
{
continue;
}
if((coef >
0)&&(!first))
{
s += "+";
}
if(((i==0)&&(j==0))||(coef*coef != 1))
{
s += coef;
}
else if(coef == -1)
{
s += "-";
}
first = false;
if(i>0)
{
if(i == 1)
{
s += "x";
}
if(i>1)
{
s += "(x^"+i+")";
}
}
if(j>0)
{
if(j == 1)
{
s += "y";
}
if(j>1)
{
s += "(y^"+j+")";
}
}
}
}
if(s.length() == 0)
{
s = "0";
}
System.out.println(s);
}
public static void main(String[] args)
{
PolyIn2DArray a = new PolyIn2DArray(3,4);
a.coef_[2][2] = 1;
a.coef_[1][0] = -10;
a.coef_[0][3] = -5;
a.coef_[0][0] = 100;
System.out.println("a=");
a.print();
PolyIn2DArray b = new PolyIn2DArray(10,4);
PolyIn2DArray z = new PolyIn2DArray(1,1);
b.coef_[3][2] = 1;
b.coef_[1][1] = -1;
b.coef_[0][0] = 1;
System.out.println("b=");
b.print();
PolyIn2DArray c = new PolyIn2DArray(1,1);
c.add(a,b);
System.out.println("a+b=");
c.print();
c.sub(a,b);
System.out.println("a-b=");
c.print();
}
}
a) Write Java code for the member methods add(PolyIn2DArray a,PolyIn2DArray b), sub(PolyIn2DArray a,PolyIn2DArray b).
b) What is the time and space complexity of your code? Be as precise as possible.
2) In this exercise you will implement matrix addition for a class representing Sparse Matrices in compact form. We use the data structure Chain to represent a row of the Sparse Matrix. And we use the array of row chains to index the rows of the Sparse Matrix (Please refer to the slide lec116.pdf). In the row chains, the elements of the chain are sorted in ascending order according to the column index. For example, for a 4 x 5
Sparse Matrix m1,
0 0 3 4 0
m1 = 0 0
5 7 0
0 0 0 0 0
0
2 6
0 0
Assuming the nodes in the chain are in the form of (index of column, key value), we represent the matrix m1 in the array of row chains as follows:
Array[0]: (2, 3) -> (3, 4) -> NULL
Array[1]: (2, 5) -> (3, 7) -> NULL
Array[2]: NULL
Array[3]: (1, 2) -> (2, 6) -> NULL
Notes:
1: The index of rows and the columns start from 0.
2: The elements of the chain are sorted in an ascending order
according to the column index.
3: The add method will check if the two matrices have the same dimensions and
print an error message if they don't.
4: The elements can be positive or negative. When an element adds up to zero,
it needs to be removed from the data structure to keep efficiency.
5: The matrix passed as an argument to the add method should not be modified in
your code.
The template for the class is given below:
package dataStructures;
class MySparseMatrix {
class SparseMatrixNode { // the node of Sparse Matrix
int column; // the column index of the node
int value; // the key value of the node
// constructor
public SparseMatrixNode(int c, int v) {
column = c;
value = v;
}
}
Chain[] rows; // the array of the row chains
protected int row_num; // the number of matrix rows
protected int column_num; // the number of matrix columns
// constructor
public MySparseMatrix(int r, int c) {
row_num = r;
column_num = c;
rows = new Chain[row_num];
for (int i = 0; i < row_num; i++) {
rows[i] = new Chain();
}
}
// May write helper methods if needed.
/**
* Get the key value of the element whose index is (i,j).
*
* @param i,j
* the row and column index of the matrix.
* @return the key value of the element whose index is (i,j).
*/
public int get(int i, int j) {
if ((i >= row_num || i < 0) || (j >= column_num || j < 0)) {
System.out.println("Out
of the bound");
return -1;
}
Chain ch =
rows[i];
for (int index
= 0; index < ch.size(); index++) {
if (((SparseMatrixNode) ch.get(index)).column
== j)
return ((SparseMatrixNode) ch.get(index)).value;
}
return 0;
}
/**
* To create or reset the element whose index is (i,j), and assign the key
* value “newValue”.
*
* @param i,j
* the row and column index of the matrix.
* @param newValue
* the key value of the the element whose index is (i,j).
*/
public void set(int i, int j, int newValue) {
if ((i
>= row_num || i < 0)
|| (j >= column_num || j < 0)) {
System.out.println("Out of the bound");
return;
}
Chain ch
= rows[i];
if (ch.size()
== 0)
ch.add(0, new SparseMatrixNode(j,
newValue));
int
index;
for (index = 0; index < ch.size(); index++) {
if (((SparseMatrixNode) ch.get(index)).column
== j) {
if (newValue == 0) {
ch.remove(index);
return;
}
((SparseMatrixNode) ch.get(index)).value = newValue;
return;
}
if (((SparseMatrixNode) ch.get(index)).column
> j) {
if (newValue != 0)
ch.add(index, new SparseMatrixNode(j, newValue));
return;
}
}
if (newValue != 0)
ch.add(index, new SparseMatrixNode(j,
newValue));
}
//print the matrix
public void printMatrix()
{
for (int i = 0; i < row_num; i++) {
for (int j = 0; j < column_num; j++) {
System.out.print(get(i, j) + " ");
}
System.out.print("element number:"+rows[i].size);
System.out.println();
}
}
/**
* Add the given matrix. In
other words, A.add(B)
should change A to A+B.
*/
public void add(MySparseMatrix
msm) {
//your code here
}
//
Please use the test code as follows.
public static void main(String[] args) {
MySparseMatrix msm1 = new MySparseMatrix(4,
5);
MySparseMatrix msm2 = new MySparseMatrix(4,
5);
msm1.set(0, 2, 1);
msm1.set(0, 2, 3);
msm1.set(0, 3, 4);
msm1.set(1, 2, 5);
msm1.set(1, 3, 7);
msm1.set(3, 1, -2);
msm1.set(3, 2, 6);
msm1.printMatrix();
msm2.set(0, 3, 3);
msm2.set(0, 2, -3);
msm2.set(2, 2, 5);
msm2.set(1, 3, 4);
msm2.set(3, 4, 3);
msm2.set(3, 2, 5);
msm2.printMatrix();
msm1.add(msm2);
msm1.printMatrix();
msm2.printMatrix();
}
}
a) You are not allowed to call
the functions defined in the Class Chain and the “get” and “set” methods in MySparseMatrix. Write Java code for
the member method void add(MySparseMatrix
msm). Make sure you test your code
extensively, as this problem might be trickier than it looks.
b) Determine and justify the time complexity of void add(MySparseMatrix msm ).