Please read carefully the homework-solving guidelines mentioned in the syllabus before you start this homework. Plagiarism is absolutely unacceptable. 1 Problem description This assignment is about SparseMatrices. A matrix looks like a 2D-array and is commonly represented using a 2D-array. Similarly, a 3D matrix is represented using a 3D array, and so on. In this assignment, we will work with 2D integer matrices only. Here is an example of a 3 4 matrix having 3 rows and 4 columns: 99 10 20 198 20 50 60 95 2 0 5 1 In computing, matrices are heavily used in graph algorithms, web-search engines, graphics, AI and machine learning, computational geometry, and in many other important areas. A matrix is sparse if it contains a very few non-zero entries. In other words, most of the entries are zeros. Here is an example of a sparse matrix having 5 rows and 4 columns: 0 89 0 0 0 0 0 5 2 0 0 125 0 0 0 0 0 0 0 0 1 Storage-space optimization has turned out to be very important in this age of Big Data. Memory price has gone down but space requirements are going up exponentially. This motivates us to look at an efficient way of storing sparse matrices both in primary (RAM) and secondary memories (files). By efficient, we mean that the space taken by a sparse matrix in a computer system should be proportional to the number of non-zero entries in the matrix instead of the number of cells in the matrix. For storing and working with large sparse matrices in real-world applications, this is indeed very helpful in practice. We will also implement the simple matrix addition operation that can add two sparse matrices. Matrix addition is a no-brainer. You just add two matrices by adding the corresponding entries together. To simply things a bit, we will work with square matrices only, meaning the number of rows will always be equal to the number of columns. In the following, we see an example of matrix addition applied on two square sparse matrices having size 5. 0 0 0 0 0 11 0 0 0 5 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 + 1 0 0 4 5 0 1 0 0 5 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 = 1 0 0 4 5 11 1 0 0 10 1 2 0 0 0 0 0 0 20 0 0 0 0 0 0 The file representation for these sparse matrices (to be used to save a sparse matrix to a file) have a specific format. The first line of such a file contains the size of the matrix (number of rows/columns; these two are the same for square matrices). Then, every following line consists of three integers i j k, where i is the row number, j is the column number, and k is the entry. The row and column numbers run from 0 to n 1 where n is the size of the matrix. For instance, a file representation for the following matrix, 0 0 0 0 0 11 0 0 0 5 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 may look like: 5 1 4 5 2 0 1 2 1 2 1 0 11 The matrix entries in a file can be in arbitrary order. This means we cannot assume that the entries are present in row-major order, column-major order, or in any other pre-defined order. 2 Here comes the interesting part! How can we efficiently represent and store a sparse matrix in the main memory (RAM). One can use a 2D-array but clearly that would be a wastage of space since most of the matrix entries are zeroes. We will implement a smart way of storing these matrices. Refer to the figure below that corresponds to the resultant matrix obtained from the example matrix addition shown before. 1 0 0 4 5 11 1 0 0 10 1 2 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 5 11 1 10 1 2 20 Every row and every column is represented using a separate doubly linked list. The pink nodes are the row doubly linked list headers and the blue nodes are the column doubly linked list headers. These headers do not store anything useful. For the sake of simplicity, we are storing zeros in them. The gray nodes store the actual matrix entries. As can be inferred from the figure, every gray node has four link fields: up, down, left, right and three Integer fields: entry, row number, and column number. Furthermore, a gray node belongs to a row doubly linked list and a column doubly linked list as well. For the pink, blue, and gray nodes, we use a common class. See below. private static class MatrixNode { Integer entry, row, col; MatrixNode up, down, left, right; // This constructor is used for creating the gray nodes only public MatrixNode(Integer row, Integer col, Integer entry) { this.entry = entry; this.row = row; this.col = col; this.up = this.down = this.left = this.right = null; } // This constructor is used for creating the headers (the pink and blue nodes) only public MatrixNode(Integer row, Integer col) { this.entry = 0; this.row = row; this.col = col; this.up = this.down = this.left = this.right = null; } } 3 We do not work with the up and down fields of the pink nodes. Similarly, we also do not work with the left and right fields of the blue nodes. Your only task is to complete the method setEntry() mentioned in the partial code that can insert a new entry into a matrix at a specified position. 2 A sample test (design a few more of your own) This sample test uses the matrix addition example show in the previous section. The two input sparse matrices are given in two separate files, as shown below. 5 1 4 5 2 0 1 2 1 2 1 0 11 5 0 4 5 0 3 4 3 3 20 0 0 1 1 4 5 1 1 1 The result obtained after adding the above two matrices (the content is written to a file): 5 0 0 1 0 3 4 0 4 5 1 0 11 1 1 1 1 4 10 2 0 1 2 1 2 3 3 20 3 The methods that are already completed for you Note that you need to work with the SparseMatrix2D class only. It is a child class of the AbstractSparseMatrix2D class. The constructor for the SparseMatrix2D class. The file-handling is already done for you. The addMatrices method from the AbstractSparseMatrix2D class. This static method adds two sparse matrices and sends the output to a file. Once again the file-handling is already done for you. A printRowMajorLtoR method from the AbstractSparseMatrix2D class.. This method prints a matrix row-wise and every row is printed from left to right. Also, a printRowMajorRtoL method that prints a matrix row-wise but every row is printed from right to left. 4 A printColMajorTtoB method from the AbstractSparseMatrix2D class.. This method prints a matrix column-wise and every row is printed from top to bottom. Also, a printColMajorBtoT method that prints a matrix column-wise but every row is printed from bottom to top. Consider the given sample test. Assume that the input matrices are given in two text files m1.txt, m2.txt. Then, for the following sequence of statements, SparseMatrix2D A = new SparseMatrix2D("m1.txt"); SparseMatrix2D B = new SparseMatrix2D("m2.txt"); SparseMatrix2D.addMatrices(A, B, "m3.txt"); SparseMatrix2D C = new SparseMatrix2D("m3.txt"); C.printRowMajorLtoR(); C.printRowMajorRtoL(); C.printColMajorTtoB(); C.printColMajorBtoT(); the expected console output is (think why and how): Row 0: <--> (0,0,1) <--> (0,3,4) <--> (0,4,5) Row 1: <--> (1,0,11) <--> (1,1,1) <--> (1,4,10) Row 2: <--> (2,0,1) <--> (2,1,2) Row 3: <--> (3,3,20) Row 4: Row 0: <--> (0,4,5) <--> (0,3,4) <--> (0,0,1) Row 1: <--> (1,4,10) <--> (1,1,1) <--> (1,0,11) Row 2: <--> (2,1,2) <--> (2,0,1) Row 3: <--> (3,3,20) Row 4: Col 0: <--> (0,0,1) <--> (1,0,11) <--> (2,0,1) Col 1: <--> (1,1,1) <--> (2,1,2) Col 2: Col 3: <--> (0,3,4) <--> (3,3,20) Col 4: <--> (0,4,5) <--> (1,4,10) Col 0: <--> (2,0,1) <--> (1,0,11) <--> (0,0,1) Col 1: <--> (2,1,2) <--> (1,1,1) Col 2: Col 3: <--> (3,3,20) <--> (0,3,4) Col 4: <--> (1,4,10) <--> (0,4,5) 4 Words of caution... 5 Understand the code outline given to you thoroughly. If you do not understand it clearly, it may take a long time to complete this assignment. But once you understand it, you can solve it fast and also get the fun out of it! Also, going through it carefully will teach you several aspects of object-oriented programming in Java. Probably you are going to get a ton of NullPointerException errors if you are working with linked lists for the first time. But do not get upset, everyone gets these errors! Just make sure that when you insert a new node, the links are set correctly. Wrongfully setting the links may garble the full matrix. Please pay special attention to the boundary cases such as, inserting at the front, inserting at the end, and inserting when the row or column doubly linked list is empty. A good programmer will always create test cases to test these special cases. While testing, act like an adversary to your code. Try to find bugs; this is how testing works. 5 What to deliver? Upload just the file SparseMatrix2D.java to Canvas. Feel free to define additional helper methods wherever needed. No need to upload anything else. In this assignment, you are not allowed to use any built-in Java data structures such as LinkedList, ArrayList, etc. Since we are learning data structures, we need to see how they work under the hood. Commenting is highly encouraged. Please test thoroughly before submission. You will be given zero if your program does not compile or gives unnecessary warnings. Please do not create any custom Java package for this submission. You are allowed to submit your solutions multiple times. We will grade your latest submission only. 6