Description

Description

• 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
• 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

∗ 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;

}

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:24.6 4:5.5
  • 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>… .

.

.

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; cinfromfile>>a>>c>>b;

//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;

}

//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 ₀
• 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)