159.201 Algorithms & Data Structures Assignment 1
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.
2023-03-14