|
|
|
|
|
|
|
|
|
|
|
|
|
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 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 2-dimensional 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*(n-1)/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 trade-off is probably worthwhile in the long-run.
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,
there are many ways of accomplishing this and since this is not a real problem (ie: this is a made-up 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:
Firstly, how are you storing your matrix - as a 2-dimensional 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 vice-versa.
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 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 Marilyn de Queiroz:
Can you state the problem in pseudocode?
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 vivekkumar sharma:
Hi,
do bit of Google
Originally posted by vivekkumar sharma:
Otherwise to detect a circle in a graph ,
keep track of nodes visited starting from a particular node,(using a set may be helpful) and if u get same node from where you started ,you have detected a circle.
Originally posted by Virag Saksena:
Tarjan's algorithm for detecting cycles will find cycles in O(n+e) time in a directed graph with n vertices and e edges.
Originally posted by jiju ka:
The 'Class' object for House is created when class 'House' is loaded. Whenever the House is refrenced by an executable statement at runtime the class is loaded.
Originally posted by Stan James:
Right, a static variable does not go out of scope. If the only reference to some large object is a static variable it will stay in scope and cannot be collected. Loaded classes can go out of scope under some very carefully constructed circumstances but just figure they are there forever.
Originally posted by Stan James:
By making something static it's possible to make a mistake where you think you're gathering objects in a cache or collection for a short time and you wind up gathering them for the whole run of the program. Any time I see a static collection I think "That could grow forever ... how do we make sure it doesn't?"[/QB]