CSC1003 Assignment 2

Important Notes

1. The assignment is an individual project, to be finished on one’s own effort.
2. The work must be submitted before 6pm Nov. 7th, 2023 (Tuesday), Beijing Time. This is a firm deadline. No late submissions are accepted.
3. Plagiarism is strictly forbidden, regardless of the role in the process. Notably, ten consecutive lines of identical codes are treated as plagiarism. Depending on the seriousness of the plagiarism, 30% − 100% marks will be deducted.
4. This assignment is supposed to be finished after learning arrays. Meanwhile, a draft may be released earlier for students’ preparation purpose.
5. Please let the teaching team know for any ambiguity or incorrectness in this draft.

Marking Criterion

1. The full score of the assignment is 100 marks.
2. Two java programs are to be submitted. Each program will be evaluated with several unseen test cases. A submission obtains the full score if and only if both programs pass all test cases.

Running Environment

1. The submissions will be evaluated in the OJ system running Java SDK. It is the students’ responsibility to make sure that his/her submissions are compatible with the OJ system.
2. The submission is only allowed to import four packages of (java.lang.; java.util.; java.math.; java.io.) included in Java SDK. No other packages are allowed.
3. All students will have an opportunity to test their programs in the OJ platform prior to the official submission.

Submission Guidelines

1. You will get your grade only if you submit your code both on OJ and on bb on time. An n-day late submission on bb leads to n ∗ 10% mark deduction, and any late submission on OJ leads to minimum grade.
2. For bb submission, you need to directly upload your java file on bb. That is, your submission should be GaussianElimination.java, or M atrixMultiplication.java, or both. Wrong submission format will receive 10% mark deduction.
3. Inconsistency with or violation from the guideline leads to marks deduction.
4. All students are reminded to read this assignment document carefully and in detail. No argument will be accepted on issues that have been specified in this document.

Program

You need to choose either ”Program A” or ”Program B” to finish. If you finish both, the higher score will be included in the overall grade.

A

In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. The method is named after Carl Friedrich Gauss (1777–1855). (see, https://en.wikipedia.org/wiki/Gaussian_elimination) You are required to write a Java program that reads the input of an augmented matrix, solve the associated system of linear equations, and then output the solution vector. For the example in Fig.1, the corresponding input and output are given in the following table.

An example of console input	Expected console output
3	2.000 3.000 -1.000
2.0 1.0 -1.0 8.0
-3.0 -1.0 2.0 -11.0
-2.0 1.0 2.0 -3.0

Note

1. The first line is a positive integer, giving the number of unknown variables of the linear equations. Let the number be n.
2. Starting from the second line, each line of the input consists of n double number separated by spaces.
3. The output is expected to be n floating point number rounded to three decimal places, giving the solution of unknown variables.
4. The template for reading input and output has been provided in GaussianElimination.java. Please strictly follow the template if you are not familiar with the output format. We have also provided the sample input and output separately in in A.txt and in A.txt. You can refer to them and use them to test your program. For command line arguments, just type
   java GaussianElimination < in A.txt
5. We promise that the input linear equations have a unique solution. That is, you don’t need
   to consider the situation the matrix doesn’t have or have multiple solutions. Also, we promise
   that you don’t need to do any row interchange.

B

Write a java program named “MatrixMultiplication.java” to calculate the product of two matrices of sizes m×n and n×p espectively. Each element of the input matrices is a complex number. (For def. of complex number, see https://brilliant.org/wiki/complex-numbers/) Therefore, the result matrix is an m×p matrix with complex elements.
In this program, each input complex number is in the form a + b ∗ i, where a, b are two positive integer smaller than 1000. For example, 3 + 89 ∗ i, 0 + 2 ∗ i, 3 + 0 ∗ i.

An example of console input	Expected console output
2 3 5
1+2i 2+3i 3+4*i	-1+66i -13+60i 14+82i -14+82i 5+76*i
1+3i 2+6i 5+2*i	1+78i 2+84i 23+98i -25+100i 9+109*i
3+4i 7+2i 5+4i 3+8i 6+3*i
5+4i 3+1i 7+3i 7+7i 9+3*i
6+3i 3+7i 8+3i 6+3i 4+4*i

Note

1. The first line of the input is the size of the two input matrices. In this example, m = 2, n =3, p = 5, each separated by a space. The following m lines give the elements of the first matrix, and each line has n space-separated complex numbers, which form the first input matrix. Then the following n lines give the elements of the second matrix, and each line has p complex numbers, which form the second input matrix.
2. The output contains m lines, each line having p space-separated complex numbers, giving the elements of the result matrix. We have provided the sample input and output separately in in B.txt and out B.txt. You can refer to them and use them to test your program. For command line arguments, just type java M atrixMultiplication < in B.txt
3. The definition of matrix and matrix multiplication operation can be found in any linear algebra textbook, or from the following link: https://en.wikipedia.org/wiki/Matrix multiplication
4. When testing the assignment, the values of m, n, p are less than 500.

Personal Answer

A

import java.util.*;

public class GaussianElimination {

    // here is the function you need to implement
    // given the augmented matrix as input, solve
    // the linear equations, and output the results
    public static void solve(double[][] augMatrix) {
        // create the solution vector
        int n = augMatrix.length;
        double[] x = new double[n];
        // your code starts here...
        for(int i=0;i<=n-2;i++){
          for(int j=i+1;j<=n-1;j++){
            double times=augMatrix[j][i]/augMatrix[i][i];
            for(int g=0;g<=n;g++){
              augMatrix[j][g]-=augMatrix[i][g]*(times);
            }
          }
        }
        for(int i=n-1;i>=0;i--){
          for(int g=i+1;g<=n-1;g++){
            augMatrix[i][n]-=augMatrix[i][g]*augMatrix[g][n];
            augMatrix[i][g]=0;
          }
          augMatrix[i][n]/=augMatrix[i][i];
          augMatrix[i][i]=1;
          x[i]=augMatrix[i][n];
        }
        

        // end of your code
        
        // output the results, DO NOT change
        for (int i = 0; i < n - 1; i++) {
            System.out.print(String.format("%.3f", x[i]) + " ");
        }
        System.out.println(String.format("%.3f", x[n-1]));
    }

    // program entry, DO NOT change
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = Integer.parseInt(input.nextLine());
        double[][] augMatrix = new double[n][n + 1];
        for (int i = 0; i < n; i++) {
            String s = input.nextLine();
            String[] t = s.split(" ");
            for (int j = 0; j < n + 1; j++) {
                augMatrix[i][j] = Double.parseDouble(t[j]);
            }
        }
        solve(augMatrix);
        input.close();
    }

}

B

import java.util.Scanner;

public class MatrixMultiplication{
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int m = input.nextInt();
    int n = input.nextInt();
    int p = input.nextInt();
    int[][][] a=new int[m][n][2];
    int[][][] b=new int[n][p][2];
    int[][][] ans=new int[m][p][2];
    int[] tmp=new int[2];
    String t="";
    String[] data=new String[2];
    for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
        t=input.next();
        data=t.split("\\+");
        a[i][j][0]=Integer.parseInt(data[0]);
        a[i][j][1]=Integer.parseInt(data[1].split("\\*")[0]);
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<p;j++){
        t=input.next();
        data=t.split("\\+");
        b[i][j][0]=Integer.parseInt(data[0]);
        b[i][j][1]=Integer.parseInt(data[1].split("\\*")[0]);
      }
    }
    for(int i=0;i<m;i++){
      for(int j=0;j<p;j++){
        tmp[0]=0;
        tmp[1]=0;
        for(int k=0;k<n;k++){
          tmp[0]+=a[i][k][0]*b[k][j][0]-a[i][k][1]*b[k][j][1];
          tmp[1]+=a[i][k][0]*b[k][j][1]+a[i][k][1]*b[k][j][0];
        }
        ans[i][j][0]=tmp[0];
        ans[i][j][1]=tmp[1];
      }
    }
    for(int i=0;i<m;i++){
      for(int j=0;j<p;j++){
        System.out.print(Integer.toString(ans[i][j][0])+"+"+Integer.toString(ans[i][j][1])+"*i"+" ");
      }
      System.out.println();
    }
  }
}