Very quickly i believe that the problem you confront is more
perceptual and at least as far as i can see you need a very good
and robust feature extraction in order to be capable to compute the
similarity (or distance in terms of machine learning/pattern
classification)between the texts, which
In order to find the median of an unsorted you can do it in O(n) time
complexity.You can do it as J.Guo said,but you need from the quicksort
the select subroutine.Try googling some keywords:
select,quicksort,median-select,k-th element.
Tarjan,etc proved that median can be done in O(n)(also i
I am also interested,please notify me .
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send
Yes you are right ,sorry..I thought something completely
different..(unfortunately..:( )
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
why don't you try a brute force technique through a simple program,to
see what it's gonna happen.You have a 4 nested loop(O(n^4))
e.g
number x=abcd
for(a=1t o 9) do
{for(b=1 to 9)do
{for(c=1 to 9)do
{for (d=1 to 9)do
{ y=1000*a+100*b+10*c+d;
if prime(y) and
one type of relaxation is based on triangle inequality.e.g
w(x1,x2)+w(x2,x3)w(x1,x3),where x1,x2,x3 are nodes(often called as
euclidean tsp),Christofides gave an algorithm with approximation ratio
1.5.
Also there are a lot of variants,you must have in mind that tsp is
np-complete ,even if the
It is true that the problem is NP-complete,albeit as DHyanesh said you
can solve it via dynamic programming,the complexity of the algorithm
is O(nW)(it is pseudopolynomial,because the W is proportional to the
input represantation,which is unfortunately exponential).
But you can find an
dear friend,i believe that a branch and bound technique would not be
ideal(even simple to implement),I believe that you can you use an A*
algorith,and try to think a good (and robust) heuristic
function,albeit the inherent combinatorial explotion can be attacked
quite efficiently(it is highly