George Lin

Ranch Hand
+ Follow
since Jan 11, 2005
Merit badge: grant badges
For More
Cows and Likes
Cows
Total received
0
In last 30 days
0
Total given
0
Likes
Total received
0
Received in last 30 days
0
Total given
0
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by George Lin

Steve,


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 ]



In my question, I mean the space complexity -- not the time complexity -- to be O(1).

Anyway, I do not quite understand your points. Could you provide some pseudo-code please?


regards,
George
18 years ago
Charles,


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...



I have found a solution to deal with the general m*n problem, please reference to "ACM Algorithm 467: Matrix Transposition in Place".

Anyway, I am very interested in the O(log[n]) time complexity algorithms, do you know where can I find related resources?


regards,
George
18 years ago
Steve,


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).



It is not from a homework. The whole requirements are too long -- so I just post a spcific requirement independent part. The total goal is to do some matrix computation with very very limited storage -- for an embedded system. The time to do the computation is not a mandatory requirement -- only the additional space required needs to be limited to a minimal level.

Anyway, do you have any good ideas?


regards,
George
18 years ago
Charles,


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.



About the storage data structure -- we can use any common data structure if transpose operation can be completed with only O(1) space complexity.

I think you mid-understand my problem a bit -- when mentioning O(1), I mean the space complexity, not the time complexity.


regards,
George
18 years ago
fred,


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.



Thank you very much for your reply!

I need to transpose the matrix PHYSICALLY in-place. When mentioning O(1), I mean the space complexity is O(1) -- not the time complexity.

Do you have any good ideas?


regards,
George
18 years ago
Steve,


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:



Your idea is very smart! But I need to transpose the matrix in-place other than from output level (showed in your sample).

Do you have any good ideas?


regards,
George
18 years ago
Marilyn,


Originally posted by Marilyn de Queiroz:
Can you state the problem in pseudocode?



I think my question is how to write pseudocode from my problem -- if I can do that, I have no question. :-)

Anyway, why you are confused with my problem, do not understand transpose of a matrix or some other points?


regards,
George
18 years ago
Steve,


Originally posted by Steve Fahlbusch:
Set a flag - true if transposed, false otherwise

Have the access methods swap the indicies if transposed.



I can not understand your idea since it is so brief. :-) Could you provide some sample implementation please? I think it just needs several lines.


regards,
George
18 years ago
Hello everyone,


I am wondering how to transpose a matrix (m * n) with only constant space
complexity O (1). (The transpose algorithm should execute/operate on the
original matrix.)


thanks in advance,
George
18 years ago
Hello everyone,


I am working on a dictionary application implementation. I have question about a string pattern matching algorithm implementation. In this algorithm, * can be used to match any sequence of characters. The input is string s1 and string s2, the algorithm using s2 to match s1, and the output is the number of possibility matching.

For example, s1 = ABC, s2 = AC*, output is 0;
For example, s1 = ABC, s2 = A*C, output is 1;
For example, s1 = AB, s2 = ***, output is 6 (AB,NULL,NULL
NULL,AB.NULL
NULL,NULL,AB
NULL,A,B
A,NULL,B
A, B, NULL);

Does anyone know what is the most efficient implementation? Currently, I only have a brute-force implementation.


thanks in advance & happy new year,
George
18 years ago
vivekkumar,


Originally posted by vivekkumar sharma:
Hi,
do bit of Google



I do made a search before I posted this question before. The issue is that, I do not know the name of the algorithm so that I can not find much useful information from Google. Could you help please? :-)

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.



I have tried this method. I do not think this method is correct. For example, suppose in a simple graph, there are four nodes, A, B, C, D. The directed graph has the following edges,

A-->B
A-->C
B-->D
C-->D

In this graph, there is no cycle. But when running your method, since node D will be accessed twice both by node B and by node C, the directed graph will be detected cycle by your method.

Maybe I do not quite understand your method, could you provide a simple implementaion of your method please?

regards,
George
18 years ago
Virag,


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.




It seems very efficient! But I can not find the algorithm you mentioned from Google by searching key words "Tarjan cycle graph". Could you help to provide more information please?


regards,
George
18 years ago
Hello everyone,


My application needs a feature to detect whether a directed graph contains circle. Does anyone know any efficient implementation? Which implementation is the best (most efficient)?


thanks in advance & happy new year,
George
18 years ago
jiju,


Your reply is great! I have only one more question about it.

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.



In the above statement, do you mean the class 'House' is loaded again and again when House is referenced by an executable statement?


regards,
George
18 years ago
Thanks Stan,


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.



- When you say "collected", do you mean garbage collected?

- In what circumstances could "loaded classes can go out of scope"? How to "figure they are there forever"? Could you provide a sample circumstance?

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]



What means "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"? Could you provide a simple sample please?


regards,
George
18 years ago