Search found 40 matches

by nnahas
Thu Jan 13, 2005 11:00 pm
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13163

Re: 10805 Cockroach Escape Networks

If you are using the algorithm by Yuqiang Guan and Kenneth Williams, you will get a wrong answer. The same goes for the official solution to a similar problem from a Romanian contest. I believe that the Guan-Williams algorithm for finding the minimum-diameter spanning tree has a mistake. Here is a ...
by nnahas
Thu Jan 13, 2005 9:24 pm
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13163

We still have to prove that the existence of T implies the existence of a BFS tree rooted at v having the same property as T (namely that all its deepest nodes are the descendants of the same child of v.) I'll leave that to a later message. Stay Tuned :) First , my remark that the code would be ver...
by nnahas
Thu Jan 13, 2005 8:32 pm
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13163

[ Case 2: The minimum diameter spanning tree T has an even diameter d(meaning the longest path has an even number of vertices.) Mmm, well, this case would be equivalent to the previous one *IF* we could prove that splitting the edge in T that links v (which is defined to be one of the two midpoints...
by nnahas
Thu Jan 13, 2005 7:10 pm
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13163

If you read the algorithm description carefully, it will try BFS(10), find that it gives a minimum diameter BFS tree, and then try to split edge 9-10, which will cause it to return 7. I e-mailed the authors, but got no reply yet. It's also unfortunate that they give no formal proof of correctness -...
by nnahas
Thu Jan 06, 2005 7:48 pm
Forum: Volume 1 (100-199)
Topic: 108 - Maximum Sum
Replies: 233
Views: 22542

Do you think you can solve this in O(n^2), because I thought only O(n^3) exists. :roll: have you got a profe on this O(n^2) theorem? I really, really don't think there's an easy O(N^2) algo for this algo (and by easy I mean necessitating less than a lifetime of research) . It's been an open problem...
by nnahas
Thu Jan 06, 2005 4:10 pm
Forum: Algorithms
Topic: Exact matching subimages
Replies: 5
Views: 1470

I think I got an O(N^3 lg(N) ) expected time algorithm . Here it is : First note that we can check whether there is a common submatrix of size W*H in O(N^2) time, (W and H are given) ,by getting a hash value for each W*H submatrix in the first matrix , putting these hash values in a hash table and t...
by nnahas
Wed Jan 05, 2005 8:15 pm
Forum: Algorithms
Topic: Exact matching subimages
Replies: 5
Views: 1470

By N I meant the size of the N*N bitmap, not the number of input bits. if you consider the number of input bits as being the input size my algo is O(N^2) , not O(N^4).
by nnahas
Wed Jan 05, 2005 4:15 pm
Forum: Algorithms
Topic: Exact matching subimages
Replies: 5
Views: 1470

OK the best I got is O(N^4). Here is how I do it: I try all possible values for (x1-x2) and (y1-y2). To check what is the maximum common submatrix with given values of (x1-x2) and (y1-y2) , I shift the matrix M2 by (x1-x2) horizontally and (y1-y2) vertically , and I obtain a new matrix M2' . (shifti...
by nnahas
Sun Dec 05, 2004 1:18 am
Forum: Algorithms
Topic: Deikstra with heap
Replies: 5
Views: 1759

the correct spelling is "Dijkstra 's algorithm." If you look it up in Google you'll see plenty of links.
by nnahas
Sun Dec 05, 2004 1:12 am
Forum: Algorithms
Topic: k-th shortest path
Replies: 2
Views: 1239

You might wish to see this web page:
http://terra.act.uji.es/REA/

Go to advanced search