Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

159.201 Algorithms & Data Structures

Assignment 1

A vector is considered sparse  when most of its entries are zero.   Sparse vectors can be represented more efficiently by storing only non-zero values and their positions.

In this assignment you need to implement vector addition for sparse vectors. You need to write and submit a program (in C/C++) that reads two sparse vectors from standard input, adds them, and prints the resulting sparse vector to standard output.  The format of sparse vectors to be used for I/O is the following:

n index1  value1  index2  value2  ... indexn  valuen

Here n denotes the number of non-zero values, valuei  the ith  non-zero value and indexi  its position in the vector. Non-zero values must be listed in ascending order of position, for both input and output. Values are positive or negative integers, small enough to be stored and added as int. A usage example is shown below.

Assuming zero-based indexing, the two vectors added here are

0  0  0  1  0  0  2  0  0  3  0  0  0  ...

+  0  0  0  0  4  0  5  0  6  0  0  0  0  . . .

=  0  0  0  1  4  0  7  0  6  3  0  0  0  . . .

Your code must represent sparse vectors in“sparse format” throughout, meaning memory consumption must only depend on the number of non-zero values (and not on the maximum index). Other than that, you may use any data structure you like.

You can use CodeRunner to test your work, but must submit your assignment as usual. If teamwork is permitted and you work in a team, you must include the names and student IDs of all team members as comments in your submission, and each team member must submit the same assignment separately.