Programming Assignment 3 Solution

This is an individual assignment. Please do not collaborate



If you think that this document does not clearly describes the assignment, ask questions before its too late. This assignment is about implementing and testing classes for sparse matrix operations.



Sparse Matrix/Vector




A sparse matrix/vector holds only the non-zero data but acts as a regular matrix/vector.






Basic Elements







SparseVector Class




Represents a single dimensional sparse data.



Requirements:



– SparseArray : Constructors




∗ Write the required constructors. For example, you need a constructor which takes a string filename data, opens the file, reads the contents, creates and populates an object.




– operator+ : Adds two SparseVectors




∗ Usage: sparse_vec_1 + sparse_vec_2.

∗ Creates another SparseVector object.

– operator- : Subtracts one SparseVector from another ∗ Similar to operator+

– operator- : Negates elements of a SparseVector




∗ Creates another SparseVector object which is element-by-element negative of the operant.

– operator= : Assigns one SparseVector to another




∗ Usage: sparse_vec_1 = sparse_vec_2

– operator<< : Sends contents of a SparseVector to a std::ostream object.




∗ Creates the text representation of a SparseVector and sends it to a std::ostream object. (See Text Representations section for more details)

– function dot : Calculates the dot product(inner product) of two SparseVectors ∗ Returns a real number (See Dot Product Section for more details)




SparseMatrix Class




Represents a two dimensional sparse data.



Requirements:



– SparseMatrix : Constructors.




∗ Similar to SparsVector class description.

– operator+ : Adds two matrices




∗ Similar to SparsVector class description.

– operator- : Subtracts one matrix from another







1
∗ Similar to SparsVector class description.

– operator- : Negates elements of a matrix




∗ Similar to SparsVector class description.

– operator= : Assigns one matrix to another ∗ Similar to SparsVector class description.

– operator<< : Sends contents of a SparseMatrix to a std::ostream object.




∗ Similar to SparsVector class description.

– operator* : Multiplies two matrices (Regular matrix multiplication) ∗ Similar to SparsVector class description.

– function transpose : Returns the transpose of a matrix




∗ Creates another SparseMatrix which is the transpose of the original object.




Driver Program




This part describes how you test various operations for the classes you created.



Your classes will be tested by a driver program. The driver program perform various SparseVector and SparseMatrix operations and incrementally fill a file with the changing contents of the objects created



Below is an example driver program.(Not all operations are shown)



#include <iostream




#include <fstream




#include <string




#include "SparseVector.h"




#include "SparseMatrix.h"




using namespace std;




int main()




{




ofstream outfile;




outfile.open("output.txt", ios::out | ios::trunc );







//Creating a SparseVector from file




SparseVector a1("a1.txt");




outfile<<"a1"<<endl<<a1<<endl;




//Binary operations and assignment




a1 = a1 + a1;




outfile<<"a1"<<endl<<a1<<endl;




//Creating SparseMatrix from file




SparseMatrix m1("m1.txt");




SparseMatrix m2("m2.txt");




outfile<<"m2"<<endl<<m2<<endl;




//Transpose




outfile<<m2.transpose()<<endl;




//Dot product




outfile<<dot(a1,a1)<<endl;




return 0;




}










2
Text Representations




Text Representation of SparseVector




format:



<index:<data <index:<data <index:<data...




index is in ascending order (natural number)



example:



4:23.8 7:10.7 10:34 12:20 1012:5




For the above example non-zero indices are 4,7,10,12,1012 Text Representation of SparseMatrix
format:



<row_index <index:<data <index:<data <index:<data...




<row_index <index:<data <index:<data <index:<data...




<row_index <index:<data <index:<data <index:<data...




.




.




.




index and row_index are in ascending order (natural numbers)



example:



3
3:24.6 4:5.5
4
1:1.15
8
5:6.4 8:34.1 9:13.1



Dot Product




Dot product of two vectors is a scalar operation



Dot product of vector_1 and vector_2:



dot_product = vector_1[0]*vector_2[0] + vector_1[1]*vector_2[1] + vector_1[2]*vector_2[2] + ...




Transpose




Matrix:



<row_index <index:<data1 <index:<data2 <index:<data3...




<row_index <index:<data4 <index:<data5 <index:<data6...




<row_index <index:<data7 <index:<data8 <index:<data9...




.




.




.




Transpose of the Matrix



<row_index <index:<data1 <index:<data4 <index:<data7...




<row_index <index:<data2 <index:<data5 <index:<data8...




<row_index <index:<data3 <index:<data6 <index:<data9...




.




.




.






















3
File I/O




File I/O objects are defined in <fstream header.




In order to write to a file, first wee need to create the file stream object. A file stream object is similar to std::cout.




For output, It is type is std::ofstream. This type is derived from std::ostream.




//create the file stream object




ofstream couttofile;




//open the file and associate it with the object couttofile.open("output.txt", ios::out | ios::trunc );




//write to stream object




couttofile<<"Test"<<endl;




couttofile<<"Test2"<<endl;




.




.




.




In order to write to a file, first wee need to create the file stream object. A file stream object is similar to std::cin.




For input, It is type is std::ifstream. This type is derived from std::istream.




//create the file stream object




ifstream cinfromfile;




//open the file and associate it with the object cinfromfile.open("input.txt");




//read "12:23.5" from stream object




int a;




double b;




char c;




cinfromfileacb;




//in order to read the a line from a file, you can use getline()




// function from <string library.




string s;




std::getline(cinfromfile, s);




//reading lines in a loop




//a helper function in order to secure file read operations int check_errors(ifstream* f) {




int stop = 0;




if (f-eof()) {




EOF after std::getline() is not the criterion to stop processing



data: In case there is data between the last delimiter and EOF,



getline() extracts it and sets the eofbit.



stop = 0;




}




if (f-fail()) {




stop = 1;




}




if (f-bad()) {




stop = 1;




}




return stop;




}










4
//Create a string




string line;




//Create an ifstream object by providing a filename // This opens the file as well

ifstream f ("file.txt");




//check if it is open




if (f.is_open())




{




while(1) {




getline(f, line);




if (check_errors(&f)) {




//skip the data processing and break




break;




}




This is the actual operation on the data obtained and we want to



protect it from errors during the last IO operation on the stream



cout << "data line " << ": " << line << endl;




}




}




Remarks




Write comments in your code.



If your code does not compile you will get 0



Do not share your code with your classmates.



Turn in:




“SparseVector.h”



“SparseMatrix.h”



.cpp implementations of classes and everything else you created.



Your code will be compiled according to the following GNU make script



You can also provide your own makefile script



Do not send any IDE specific files.



SRC_DIR := .




OBJ_DIR := .




SRC_FILES := $(wildcard $(SRC_DIR)/*.cpp)




OBJ_FILES := $(patsubst $(SRC_DIR)/%.cpp,$(OBJ_DIR)/%.o,$(SRC_FILES))




LDFLAGS := ...




CPPFLAGS := ...




CXXFLAGS := ...




main.out: $(OBJ_FILES)




g++ $(LDFLAGS) -o $@ $^




$(OBJ_DIR)/%.o: $(SRC_DIR)/%.cpp




g++ $(CPPFLAGS) $(CXXFLAGS) -c -o $@ $<




CPPFLAGS += -std=c++11




CXXFLAGS += -MMD




-include $(OBJ_FILES:.o=.d)










5
Late Submission




(0,24] hours: -20%



(24,48] hours: -40%



(48,72] hours: -60%



(72,-) hours: -100%


























































































































































































6