Jump to content

Check out our Community Blogs

sensationality's Content

There have been 4 items by sensationality (Search limited from 09-December 18)

Sort by                Order  

#594682 Matrix mulitplication using Linked List

Posted by sensationality on 20 March 2011 - 08:38 PM in C and C++

I have to implement Matrix multiplication using singly linked list. The matrices are sparse matrices so only non-zero elements are stored in the list.

For example

0 2 1
0 0 2

would be represented as the (value, position): (2,1) --> (1,2) --> (2,5)

Anyways, I have completed most methods (inverse, transpose, determinant, add, subtract, etc.) I am having troubling implementing a method which multiplies matrix 1 with matrix 2 in O(s1 * s2) run-time, where s1 and s2 are the number of non-zero nodes in the list.

So far, I have checked if they have the right index for multiplication and declared the new result list.

I actually have no idea how to start the multiplication! I know you multiply row by column through the matrix, but this would be more than O(s1 s2) time since you have to constantly move through the 2nd list to get to row 1, column 1, then row 2 column 1, then row 3 column 1, etc while moving through list 1 as row 1 column 1, row 1 column 2, etc (the latter of these isnt the problem, the first one, moving through each column is my concern) ... How do I implement with this runtime restriction?

If anyone has any idea it would be great! Thanks

#594636 Need help with logic in my program

Posted by sensationality on 20 March 2011 - 11:53 AM in C and C++

Thank you so much for your help.

I used merge sort after getting the new location for each element in my list. After sorting it with merge sort I was able to get a transpose.

Thanks again for the help gregwarner!

#594461 Need help with logic in my program

Posted by sensationality on 18 March 2011 - 08:51 AM in C and C++

Thanks a lot for your reply. That function indeed works (as I have tested with a few test cases), and I was trying to come up with something similar for quite a while. Thanks for the assistance.

Well, now I can get the new position of the elements in the list. However, the following is my concern now: Once I get the new position, in order to put the value in the new position, I would have to create another pointer and transverse the list accordingly. However, this would lead to O(s^2) run time. The assignment specification says:

"Method transpose must have running time O(s log s), where s is the number of
nonzero elements in the matrix"

Would there be any way to do this in O(s log s) time? This is why I was thinking you would to recursively switch the list.

#594452 Need help with logic in my program

Posted by sensationality on 18 March 2011 - 06:30 AM in C and C++


I am making a program which stores a matrix (2D) as a list (linked list) of 1 dimension, where each node in the list stores the value and position of the element in the matrix, as well as the next node. Furthermore, only non-zero elements (value and position) from the matrix must be stored in the list

For example

0 2 1
0 0 2

would be represented as the (value, position): (2,1) --> (1,2) --> (2,5)

My problem is, given only the list without the actual 2D representation of the matrix, I need to find the transpose of the list (matrix). Transpose is found by switching the rows and columns.

The transpose of the above example would be:

0 0
2 0
1 2

and the list now becomes (2,2) --> (1,4) --> (2,5).

I was wondering if someone can guide me on the logic of how to do this. I was thinking I'd have to use recursion somehow, but I am not sure, exactly what I would do.

Thanks in advance

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download