- Questions & Answers
- Accounting
- Computer Science
- Automata or Computationing
- Computer Architecture
- Computer Graphics and Multimedia Applications
- Computer Network Security
- Data Structures
- Database Management System
- Design and Analysis of Algorithms
- Information Technology
- Linux Environment
- Networking
- Operating System
- Software Engineering
- Big Data
- Android
- iOS
- Matlab

- Economics
- Engineering
- Finance
- Thesis
- Management
- Science/Math
- Statistics
- Writing
- Dissertations
- Essays
- Programming
- Healthcare
- Law

- Log in | Sign up

Please find it attached, upload a zip file with all the files, thank you

CSE 101 Introduction to Data Structures and Algorithms Programming Assignment 4 In this assignment you will create a calculator for performing matrix operations that exploits the (expected) sparseness of its matrix operands. An ? × ? square matrix is said to be sparse if the number of non-zero entries (here abbreviated NNZ) is small compared to the total number of entries ?2. The result will be a C program capable of performing fast matrix operations, even on very large matrices, provided they are sparse. Given ? × ? matrices A and B, their product ? = ? ⋅ ? is the ? × ? matrix whose ??th entry is given by ??? = ∑ ??? ? ?=1 ???. Thus the element in the ith row and jth column of C is the vector dot product of the ith row of A with the jth column of B. If we consider addition and multiplication of real numbers to be our basic operations, then the above formula can be computed in time Θ(?3), which is impractical for matrix sizes n of more than a few thousand. If it so happens that A and B are sparse, then a great many of these arithmetic operations involve adding or multiplying by zero, hence are unnecessary. The sum S, and difference D, of A and B are the ? × ? matrices having ??th entries: ??? = ??? + ??? and ??? = ??? − ??? The scalar product of a real number x with A is denoted ??, and has ??th entry (??)?? = ? ⋅ ???. The transpose of A, denoted ??, is the matrix whose ???ℎ entry is the ???ℎ entry of A: (??)?? = ???. In other words, the rows of A are the columns of ??, and the columns of A are the rows of ??. Each of these operations can be computed in time Θ(?2), and just as for multiplication, their cost can be improved upon significantly when A and B are sparse. As one would expect, the cost of a matrix operation depends heavily on the choice of data structure used to represent its matrix operands. There are several ways to represent a square matrix with real entries. The standard approach is to use a 2-dimensional ? × ? array of doubles. The advantage of this representation is that all of the above matrix operations have a straight-forward implementation using nested loops. This project will use a very different representation however. Here you will represent a matrix as a 1-dimensional array of Lists. Each List will represent one row of the Matrix, but only the non-zero entries will be stored. Therefore List elements must store, not just the matrix entries, but the column index in which those entries reside. For example, the matrix below would have the following representation as an array of Lists. ? = [ 1.0 0.0 2.0 3.0 0.0 0.0 0.0 4.0 5.0 ] Array of Lists: [ 1: (1, 1.0) (3, 2.0) 2: (1, 3.0) 3: (2, 4.0) (3, 5.0) This method obviously results in a substantial space savings when the Matrix is sparse. In addition, the standard matrix operations defined above can be performed more efficiently on sparse matrices. As you will see though, the matrix operations are much more difficult to implement using this representation. The trade-off then, is a gain in space and time efficiency for sparse matrices, at the expense of more complicated algorithms for performing standard matrix operations. Designing these algorithms in terms of our List ADT operations will constitute the majority of the work you do on this assignment. It will be necessary to first make some minor changes to your List ADT from pa1. First you must convert your ADT from a List of ints to a List of generic pointers. This entails changing certain field types, declaration statements, method parameters, and return types from int to void*. The objects referred to by these List elements will be defined in the Matrix ADT specified below. Second, it will be necessary to eliminate the List operations equals() and copy(). The problem with these functions is that the List no longer knows what it is a list of, and therefore can only perform "shallow" versions of these operations, i.e. compare or copy pointers, not what they point to. For the same reason, function printList() is no longer required (but you may wish to include it for diagnostic purposes only). The (optional) function cat() may also be included. All other List operations from pa1 will be retained. A "typical loop" in a client of List (as previously illustrated on page 3 of the pa1 project description) might now appear as type x; // Here "type" is whatever data type the void // pointers in List are pointing to, known by // the client but not by List. moveFront(L); while( index(L)>=0 ){ // Get current element, cast as the right kind of // pointer, follow the pointer, assign its value to x. x = *(type*)get(L); // do something with x, then moveNext(L); } Observe that the equals(), copy() and printList() operations can still be performed, but they must now be done from the client level. Be sure to test this modified List ADT before you try to implement the Matrix ADT defined below. A (very weak) test of the modified List ADT called ListClient.c will be posted under the examples section of the class webpage. File Formats The top level client module for this project will be called Sparse.c. It will take two command line arguments giving the names of the input and output files, respectively. The input file will begin with a single line containing three integers n, a and b, separated by spaces. The second line will be blank, and the following a lines will specify the non-zero entries of an ? × ? matrix A. Each of these lines will contain a space separated list of three numbers: two integers and a double, giving the row, column, and value of the corresponding matrix entry. After another blank line, will follow b lines specifying the non-zero entries of an ? × ? matrix B. For example, the two matrices ? = [ 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 ] and ? = [ 1.0 0.0 1.0 0.0 0.0 0.0 1.0 1.0 1.0 ] are encoded by the following input file: 3 9 5 1 1 1.0 1 2 2.0 1 3 3.0 2 1 4.0 2 2 5.0 2 3 6.0 3 1 7.0 3 2 8.0 3 3 9.0 1 1 1.0 1 3 1.0 3 1 1.0 3 2 1.0 3 3 1.0 Your program will read an input file as above, initialize and build the Array-of-Lists representation of the matrices A and B, then calculate and print the following matrices to the output file: ?, ?, (1.5)?, ? + ?, ? + ?, ? − ?, ? − ?, ??, ?? and ?2. The output file format is illustrated by the following example, which corresponds to the above input file. A has 9 non-zero entries: 1: (1, 1.0) (2, 2.0) (3, 3.0) 2: (1, 4.0) (2, 5.0) (3, 6.0) 3: (1, 7.0) (2, 8.0) (3, 9.0) B has 5 non-zero entries: 1: (1, 1.0) (3, 1.0) 3: (1, 1.0) (2, 1.0) (3, 1.0) (1.5)*A = 1: (1, 1.5) (2, 3.0) (3, 4.5) 2: (1, 6.0) (2, 7.5) (3, 9.0) 3: (1, 10.5) (2, 12.0) (3, 13.5) A+B = 1: (1, 2.0) (2, 2.0) (3, 4.0) 2: (1, 4.0) (2, 5.0) (3, 6.0) 3: (1, 8.0) (2, 9.0) (3, 10.0) A+A = 1: (1, 2.0) (2, 4.0) (3, 6.0) 2: (1, 8.0) (2, 10.0) (3, 12.0) 3: (1, 14.0) (2, 16.0) (3, 18.0) B-A = 1: (2, -2.0) (3, -2.0) 2: (1, -4.0) (2, -5.0) (3, -6.0) 3: (1, -6.0) (2, -7.0) (3, -8.0) A-A = Transpose(A) = 1: (1, 1.0) (2, 4.0) (3, 7.0) 2: (1, 2.0) (2, 5.0) (3, 8.0) 3: (1, 3.0) (2, 6.0) (3, 9.0) A*B = 1: (1, 4.0) (2, 3.0) (3, 4.0) 2: (1, 10.0) (2, 6.0) (3, 10.0) 3: (1, 16.0) (2, 9.0) (3, 16.0) B*B = 1: (1, 2.0) (2, 1.0) (3, 2.0) 3: (1, 2.0) (2, 1.0) (3, 2.0) Notice that the rows are to be printed in column sorted order, and zero rows are skipped altogether. A zero matrix will cause no output to be printed, as seen by the matrix ? − ? above. Note that, unlike the output file, the input file may give matrix entries in any order. Matrix ADT Specifications In addition to the main program Sparse.c and the altered List.c from pa1, you will implement a Matrix ADT in a file called Matrix.c. This ADT will contain a private inner struct (similar to Node in your List ADT) encapsulating the column and value information corresponding to a matrix entry. You can give this inner struct any name you wish, but I will refer to it here as Entry. Thus Entry is a pointer to a struct called EntryObj that has two fields of types int and double respectively. Your Matrix ADT will represent a matrix as an array of Lists of Entries. Since Entry is itself a pointer, it can be assigned to a field of type void*. It is required that each List of Entries be maintained in column sorted order. Your Matrix ADT will export the following operations. // newMatrix() // Returns a reference to a new nXn Matrix object in the zero state. Matrix newMatrix(int n) // freeMatrix() // Frees heap memory associated with *pM, sets *pM to NULL. void freeMatrix(Matrix* pM); // Access functions // size() // Return the size of square Matrix M. int size(Matrix M); // NNZ() // Return the number of non-zero elements in M. int NNZ(Matrix M); // equals() // Return true (1) if matrices A and B are equal, false (0) otherwise. int equals(Matrix A, Matrix B); // Manipulation procedures // makeZero() // Re-sets M to the zero Matrix state. void makeZero(Matrix M); // changeEntry() // Changes the ith row, jth column of M to the value x. // Pre: 1<><=size(m),><><=size(m) void changeentry(matrix m, int i, int j, double x); // matrix arithmetic operations // copy() // returns a reference to a new matrix object having the same entries as a. matrix copy(matrix a); // transpose() // returns a reference to a new matrix object representing the transpose // of a. matrix transpose(matrix a); // scalarmult() // returns a reference to a new matrix object representing xa. matrix scalarmult(double x, matrix a); // sum() // returns a reference to a new matrix object representing a+b. // pre: size(a)==size(b) matrix sum(matrix a, matrix void="" changeentry(matrix="" m,="" int="" i,="" int="" j,="" double="" x);="" matrix="" arithmetic="" operations="" copy()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" having="" the="" same="" entries="" as="" a.="" matrix="" copy(matrix="" a);="" transpose()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" representing="" the="" transpose="" of="" a.="" matrix="" transpose(matrix="" a);="" scalarmult()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" representing="" xa.="" matrix="" scalarmult(double="" x,="" matrix="" a);="" sum()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" representing="" a+b.="" pre:="" size(a)="=size(B)" matrix="" sum(matrix="" a,="">

CSE 101 Introduction to Data Structures and Algorithms Programming Assignment 4 In this assignment you will create a calculator for performing matrix operations that exploits the (expected) sparseness of its matrix operands. An ? × ? square matrix is said to be sparse if the number of non-zero entries (here abbreviated NNZ) is small compared to the total number of entries ?2. The result will be a C program capable of performing fast matrix operations, even on very large matrices, provided they are sparse. Given ? × ? matrices A and B, their product ? = ? ⋅ ? is the ? × ? matrix whose ??th entry is given by ??? = ∑ ??? ? ?=1 ???. Thus the element in the ith row and jth column of C is the vector dot product of the ith row of A with the jth column of B. If we consider addition and multiplication of real numbers to be our basic operations, then the above formula can be computed in time Θ(?3), which is impractical for matrix sizes n of more than a few thousand. If it so happens that A and B are sparse, then a great many of these arithmetic operations involve adding or multiplying by zero, hence are unnecessary. The sum S, and difference D, of A and B are the ? × ? matrices having ??th entries: ??? = ??? + ??? and ??? = ??? − ??? The scalar product of a real number x with A is denoted ??, and has ??th entry (??)?? = ? ⋅ ???. The transpose of A, denoted ??, is the matrix whose ???ℎ entry is the ???ℎ entry of A: (??)?? = ???. In other words, the rows of A are the columns of ??, and the columns of A are the rows of ??. Each of these operations can be computed in time Θ(?2), and just as for multiplication, their cost can be improved upon significantly when A and B are sparse. As one would expect, the cost of a matrix operation depends heavily on the choice of data structure used to represent its matrix operands. There are several ways to represent a square matrix with real entries. The standard approach is to use a 2-dimensional ? × ? array of doubles. The advantage of this representation is that all of the above matrix operations have a straight-forward implementation using nested loops. This project will use a very different representation however. Here you will represent a matrix as a 1-dimensional array of Lists. Each List will represent one row of the Matrix, but only the non-zero entries will be stored. Therefore List elements must store, not just the matrix entries, but the column index in which those entries reside. For example, the matrix below would have the following representation as an array of Lists. ? = [ 1.0 0.0 2.0 3.0 0.0 0.0 0.0 4.0 5.0 ] Array of Lists: [ 1: (1, 1.0) (3, 2.0) 2: (1, 3.0) 3: (2, 4.0) (3, 5.0) This method obviously results in a substantial space savings when the Matrix is sparse. In addition, the standard matrix operations defined above can be performed more efficiently on sparse matrices. As you will see though, the matrix operations are much more difficult to implement using this representation. The trade-off then, is a gain in space and time efficiency for sparse matrices, at the expense of more complicated algorithms for performing standard matrix operations. Designing these algorithms in terms of our List ADT operations will constitute the majority of the work you do on this assignment. It will be necessary to first make some minor changes to your List ADT from pa1. First you must convert your ADT from a List of ints to a List of generic pointers. This entails changing certain field types, declaration statements, method parameters, and return types from int to void*. The objects referred to by these List elements will be defined in the Matrix ADT specified below. Second, it will be necessary to eliminate the List operations equals() and copy(). The problem with these functions is that the List no longer knows what it is a list of, and therefore can only perform "shallow" versions of these operations, i.e. compare or copy pointers, not what they point to. For the same reason, function printList() is no longer required (but you may wish to include it for diagnostic purposes only). The (optional) function cat() may also be included. All other List operations from pa1 will be retained. A "typical loop" in a client of List (as previously illustrated on page 3 of the pa1 project description) might now appear as type x; // Here "type" is whatever data type the void // pointers in List are pointing to, known by // the client but not by List. moveFront(L); while( index(L)>=0 ){ // Get current element, cast as the right kind of // pointer, follow the pointer, assign its value to x. x = *(type*)get(L); // do something with x, then moveNext(L); } Observe that the equals(), copy() and printList() operations can still be performed, but they must now be done from the client level. Be sure to test this modified List ADT before you try to implement the Matrix ADT defined below. A (very weak) test of the modified List ADT called ListClient.c will be posted under the examples section of the class webpage. File Formats The top level client module for this project will be called Sparse.c. It will take two command line arguments giving the names of the input and output files, respectively. The input file will begin with a single line containing three integers n, a and b, separated by spaces. The second line will be blank, and the following a lines will specify the non-zero entries of an ? × ? matrix A. Each of these lines will contain a space separated list of three numbers: two integers and a double, giving the row, column, and value of the corresponding matrix entry. After another blank line, will follow b lines specifying the non-zero entries of an ? × ? matrix B. For example, the two matrices ? = [ 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 ] and ? = [ 1.0 0.0 1.0 0.0 0.0 0.0 1.0 1.0 1.0 ] are encoded by the following input file: 3 9 5 1 1 1.0 1 2 2.0 1 3 3.0 2 1 4.0 2 2 5.0 2 3 6.0 3 1 7.0 3 2 8.0 3 3 9.0 1 1 1.0 1 3 1.0 3 1 1.0 3 2 1.0 3 3 1.0 Your program will read an input file as above, initialize and build the Array-of-Lists representation of the matrices A and B, then calculate and print the following matrices to the output file: ?, ?, (1.5)?, ? + ?, ? + ?, ? − ?, ? − ?, ??, ?? and ?2. The output file format is illustrated by the following example, which corresponds to the above input file. A has 9 non-zero entries: 1: (1, 1.0) (2, 2.0) (3, 3.0) 2: (1, 4.0) (2, 5.0) (3, 6.0) 3: (1, 7.0) (2, 8.0) (3, 9.0) B has 5 non-zero entries: 1: (1, 1.0) (3, 1.0) 3: (1, 1.0) (2, 1.0) (3, 1.0) (1.5)*A = 1: (1, 1.5) (2, 3.0) (3, 4.5) 2: (1, 6.0) (2, 7.5) (3, 9.0) 3: (1, 10.5) (2, 12.0) (3, 13.5) A+B = 1: (1, 2.0) (2, 2.0) (3, 4.0) 2: (1, 4.0) (2, 5.0) (3, 6.0) 3: (1, 8.0) (2, 9.0) (3, 10.0) A+A = 1: (1, 2.0) (2, 4.0) (3, 6.0) 2: (1, 8.0) (2, 10.0) (3, 12.0) 3: (1, 14.0) (2, 16.0) (3, 18.0) B-A = 1: (2, -2.0) (3, -2.0) 2: (1, -4.0) (2, -5.0) (3, -6.0) 3: (1, -6.0) (2, -7.0) (3, -8.0) A-A = Transpose(A) = 1: (1, 1.0) (2, 4.0) (3, 7.0) 2: (1, 2.0) (2, 5.0) (3, 8.0) 3: (1, 3.0) (2, 6.0) (3, 9.0) A*B = 1: (1, 4.0) (2, 3.0) (3, 4.0) 2: (1, 10.0) (2, 6.0) (3, 10.0) 3: (1, 16.0) (2, 9.0) (3, 16.0) B*B = 1: (1, 2.0) (2, 1.0) (3, 2.0) 3: (1, 2.0) (2, 1.0) (3, 2.0) Notice that the rows are to be printed in column sorted order, and zero rows are skipped altogether. A zero matrix will cause no output to be printed, as seen by the matrix ? − ? above. Note that, unlike the output file, the input file may give matrix entries in any order. Matrix ADT Specifications In addition to the main program Sparse.c and the altered List.c from pa1, you will implement a Matrix ADT in a file called Matrix.c. This ADT will contain a private inner struct (similar to Node in your List ADT) encapsulating the column and value information corresponding to a matrix entry. You can give this inner struct any name you wish, but I will refer to it here as Entry. Thus Entry is a pointer to a struct called EntryObj that has two fields of types int and double respectively. Your Matrix ADT will represent a matrix as an array of Lists of Entries. Since Entry is itself a pointer, it can be assigned to a field of type void*. It is required that each List of Entries be maintained in column sorted order. Your Matrix ADT will export the following operations. // newMatrix() // Returns a reference to a new nXn Matrix object in the zero state. Matrix newMatrix(int n) // freeMatrix() // Frees heap memory associated with *pM, sets *pM to NULL. void freeMatrix(Matrix* pM); // Access functions // size() // Return the size of square Matrix M. int size(Matrix M); // NNZ() // Return the number of non-zero elements in M. int NNZ(Matrix M); // equals() // Return true (1) if matrices A and B are equal, false (0) otherwise. int equals(Matrix A, Matrix B); // Manipulation procedures // makeZero() // Re-sets M to the zero Matrix state. void makeZero(Matrix M); // changeEntry() // Changes the ith row, jth column of M to the value x. // Pre: 1<><=size(m),><><=size(m) void changeentry(matrix m, int i, int j, double x); // matrix arithmetic operations // copy() // returns a reference to a new matrix object having the same entries as a. matrix copy(matrix a); // transpose() // returns a reference to a new matrix object representing the transpose // of a. matrix transpose(matrix a); // scalarmult() // returns a reference to a new matrix object representing xa. matrix scalarmult(double x, matrix a); // sum() // returns a reference to a new matrix object representing a+b. // pre: size(a)==size(b) matrix sum(matrix a, matrix void="" changeentry(matrix="" m,="" int="" i,="" int="" j,="" double="" x);="" matrix="" arithmetic="" operations="" copy()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" having="" the="" same="" entries="" as="" a.="" matrix="" copy(matrix="" a);="" transpose()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" representing="" the="" transpose="" of="" a.="" matrix="" transpose(matrix="" a);="" scalarmult()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" representing="" xa.="" matrix="" scalarmult(double="" x,="" matrix="" a);="" sum()="" returns="" a="" reference="" to="" a="" new="" matrix="" object="" representing="" a+b.="" pre:="" size(a)="=size(B)" matrix="" sum(matrix="" a,="">

Answered 2 days AfterFeb 09, 2023

SOLUTION.PDF## Answer To This Question Is Available To Download

- Week 7: Overviewhttps://www.linkedin.com/pulse/using-rapidminer-time-series-forecasting-i-alkiviadis-vazacopoulos/Week IntroductionIn Week 7, we consider Special Topics in Data Mining, to...SolvedJun 17, 2024
- Submit your completed written assignment by Day 7 of this week.ASSIGNMENT 13: Week 7 ReportWrite a composition in which you substantively describe one of the following topics and then apply the...Jun 10, 2024
- Submit your completed written assignment by Day 7 of this week.ASSIGNMENT 13: Week 7 ReportWrite a composition in which you substantively describe one of the following topics and then apply the...Jun 10, 2024
- AssignmentSubmit your completed written assignment by Day 7 of this week.ASSIGNMENT 11: Week 6 ReportWrite a composition in which you substantively describe one of the following topics...SolvedJun 03, 2024
- IT IS VERY IMPORTANT TO READ THEINSTRUCTIONS!!! THIS IS DOCTORAL WORK. Turnitin and Waypoint are being used to check for plagiarism, and please use APA format. Please pay close attention I NEED...SolvedJun 01, 2024
- Submit your completed written assignment by Day 7 of this week.ASSIGNMENT 8: Week 5 ReportWrite a composition in which you substantively describe one of the following topics and then apply the...SolvedMay 28, 2024
- AssignmentSubmit your completed written assignment by Day 7 of this week. For detailed instructions on completing this assignment, see the associated course page.ASSIGNMENT 7: Week 4 ReportWrite a...SolvedMay 20, 2024
- AssignmentSubmit your completed written assignment by Day 7 of this week.Write a composition in which you substantively describe one of the following topics and then apply the topic you selected to...SolvedMay 13, 2024
- Instructions:Submit two files for this assignment: One MS Word file containing the required composition and one MS Excel file containing the data set selected and downloaded by the student....SolvedMay 08, 2024
- You are asked to Create a C++ program to read a large number of randomlong integersfrom a file and then determine themedianof those numberswithout sorting them. Your program should read in the...SolvedMay 02, 2024

Copy and Paste Your Assignment Here

Copyright © 2024. All rights reserved.