JavaBeginnersFaq
"Yesterday is history, tomorrow is a mystery, and today is a gift; that's why they call it the present." Eleanor Roosevelt
Originally posted by Steve Fahlbusch:
Set a flag  true if transposed, false otherwise
Have the access methods swap the indicies if transposed.
Originally posted by Marilyn de Queiroz:
Can you state the problem in pseudocode?
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
Originally posted by Steve Fahlbusch:
Assuming that you have some implemenation of matrix that will allow for direct access to any element. So you have an accessor:
getElement( i, j )
Which will return the ith,jth element of the matrix: return matrix( i, j )
change that to:
Originally posted by fred rosenberger:
do you need to PHYSICALLY transpose the matrix? or do you just need to ACCESS the transposed matrix?
if you need (for some reason) to actually move the elements around, you can't do it in O(1).
But if all you have to do is access an element of the transposed matrix, then Steve has given you the answer.
What is a transposed matrix? it is the matrix created when every element at (x,y) gets moved to position (y,x). so really, all you have to do is access the elements in a different way, and you're done.
Originally posted by Charles Lyons:
Firstly, how are you storing your matrix  as a 2dimensional array, a collection of objects or something else?
I don't think it is possible to do an O(1) transposition, unless you've got some clever OO mechanism which can simply relabel a row as a column and viceversa.
Originally posted by Steve Fahlbusch:
George,
there are many ways of accomplishing this and since this is not a real problem (ie: this is a madeup homework assignment) why don't you post the full requirements, that way we can address you solution to the problem statement.
For instance, if this is for a data structures course the approach might be much differnt than an algorithms course. (and my previous posts reflected an approach i would expect from my students, but lets see what is expected).
Originally posted by Charles Lyons:
My apologies  mostly the talk is about time complexity because memory is so cheap these days, so naturally I assumed this was your intention!
Now, I'm a little rusty on complexities, so please say if I'm talking rubbish. O(1) space complexity means the algorithm uses the same amount of storage memory space regardless of how large the input is.
I'm going to assume you're using a 2dimensional array to store the data, and since that array could be of any datatype, I'll call it "Arr[][]". I'll let the first dimension be the rows, and the second the columns within each row. For an m x n matrix we therefore have Arr[m][n]. Clearly this array will have to be as large the matrix, and therefore will occupy more memory space for larger input  but this isn't the fault of the algorithm (only the input).
To be honest, I can't see a way to transpose a general m x n matrix without having a second Arr[n][m] array to put it in. We cannot dereference the first array to resize it, then reference its entries! We would have to have two arrays in memory.
However, we can optimise for a square n x n array with data Arr[n][n], since they we don't have to change the sizes of each dimension. We can create an O(1) space algorithm by swapping entries on either side of the principle diagonal, and I think this sketch should do it:
I think that should give O(1) space complexity  we are only declaring i, j and swap for each iteration, and these will always be declared for any size array. In addition, we only have swap for those entries above the diagonal, which is significantly less than half the matrix  for an n x n this is actually n*(n1)/2.
The time complexity of this algorithm is O(n^2), making it inefficient. As I said previously, there are O(log[n]) algorithms, but they use caching of pieces of the matrix for efficiency, and this increases the space complexity. I would think this tradeoff is probably worthwhile in the longrun.
I'm not so sure about the general m x n problem  please repost if you can clarify or have any further ideas...
Originally posted by Steve Fahlbusch:
George,
I would still set a flag, and swap the indices in all of the accessors.
Size complexity ( 1 bit  boolean value )
Time complexity O(1)
 so as i said earlier, change the accesors to check the flag and all setters/getters using swapped indicies
[ January 09, 2006: Message edited by: Steve Fahlbusch ]
Originally posted by Jeff Verdegan:
George, I helped you in Sun's forums. That's the last time I help you here or there. You should know better than to crosspost by now.
Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
Time is mother nature's way of keeping everything from happening at once. And this is a tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardenergift.com
