Description
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
#include
#include
#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"<
• 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:
.
.
.
• 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:
.
.
.
• Transpose of the Matrix
.
.
.
3
File I/O
File I/O objects are defined in
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"<
//in order to read the a line from a file, you can use getline()
// function from
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
