@sravanreddy i dont think that will work,
On Fri, Jan 6, 2012 at 9:01 PM, sravanreddy001 sravanreddy...@gmail.comwrote:
@dabbcomputers: looking at the worstcase, listing all points in the set
itself takes O(n) time,
just to speed up the time would be sort all the points(x,y) wrt x-values
this problem is solved in O(n*s), where n is the size of Array and s is the
sum, the aproach is Dynamic Programming.
2012/1/6 saurabh singh saurab...@gmail.com
@all Yes it is possible to find the solution using 0/1 knapsack.The
approach would be similar as in case of LCS problem when many
@ Adolfo : little more detail about your approach will be helpful.
On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto adol...@gmail.com wrote:
this problem is solved in O(n*s), where n is the size of Array and s is
the sum, the aproach is Dynamic Programming.
2012/1/6 saurabh singh
@all
Check the link that i have provided above.. It solves the problem
using DP..
On Jan 7, 7:15 pm, atul anand atul.87fri...@gmail.com wrote:
@ Adolfo : little more detail about your approach will be helpful.
On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto adol...@gmail.com wrote:
this
@Anurag...
'SuperSum' can be reduced to the following form..
SuperSum ( k, n) = SuperSum (k-1, n) * (n+k) / (k+1) ..
Time Complexity : O(K) , Space Complexity : O(1)
Code:
int getSuperSum(int k, int n)
{
int superSum = n; // SuperSum(0, n)
int i = 0;
while( ++i = k)
{
@Lucifier:
i guess you made some editing mistake :-
Initialize the array with the following values,
1) A[0, j] = 0 for 1 = j = Wmax
2) A[i, 0] = 1 for 0 = i = Wmax // it shoud be 1 for 0 = i =N
about this equation :-
A[i , j] = A[i-1, j] | A[ i-1 , j - W[i] ]
say if W[i]=10 and j=3 , i
@Don : what would be the complexity of your alogithm??
On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:
Given an array A[n], start by sorting the array.
Then do something like this:
int result[n];
int size=0;
void findSubset(int sum, int position=0)
{
if (sum == 0)
@atul..
I thought that check would be obvious as i didn't put in the code.. so
when the code is written for the second option we need to also check
for j-W[i] =0..
:)...
On Jan 7, 9:15 pm, atul007 atul.87fri...@gmail.com wrote:
@Lucifier:
i guess you made some editing mistake :-
Initialize
@atul..
So following the above previous posted link.. the time complexity
would be 4*n = O(n)...
[ just adding it here, because i saw that u went thru the link.. :)]
On Jan 7, 9:30 pm, atul anand atul.87fri...@gmail.com wrote:
@Don : what would be the complexity of your alogithm??
On
@Lucifer : thats okbut you are using bitwise OR to fill up the array
A[].
if condition does not fullfill then wat to do to fill A[i,j] ??
i guess take it 0 if it does not fullfill..
A[i , j] = A[i-1, j] | 0 // A[ i-1 , j - W[i] ] check fail
i didnt read your whole algorithm so i
To remove duplicate combination in DON code...here is the modified code:-
Given an array A[n], start by sorting the array.
Then do something like this:
int result[n];
int size=0;
int prev=-1; // added
void findSubset(int sum, int position=0)
{
if (sum == 0) output(result, size);
for(int i
If the graph is planar and you have it's embedding, then you can do
better than O(N), at least on a random graph. Otherwise this has to be
impossible because the graph gives you no information, and you must
look at each vertex.
On Jan 5, 1:17 pm, dabbcomputers dabbcomput...@gmail.com wrote:
you
@Lucifer :
for W[]={1,3,2,1,2} and Wmax=4.
this array will be formed.
0
1
2
3
4
0
1
0
0
0
0
1
1
1
0
0
0
3
1
1
0
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
is it printing all subset ?? if yes then may be i am not getting it..
btw one query :-
b) if
On Jan 5, 4:17 am, dabbcomputers dabbcomput...@gmail.com wrote:
you are given with N points on graph. and a point A on graph and range
R you have to find the points that lies within the radius of R from
point A. with complexity less than O(N).
Why does it have to be done with less complexity
@Gene: I didn't understand on what you termed as embedding Can you
provide more insights on this?
@dabbcomputers: also, listing set of points (not just one) isn't going to
be a better than O(n) solution.
for eg: a value of R that eliminates only half the points outside the
circle.
--
You
An embedding is the information that says how the graph is laid out
with no edges crossing. As a data structure, it can be given in
various ways. The simplest is for adjacency lists of each vertex to
be given in sorted order clockwise or anti-clockwise.
On Jan 7, 5:10 pm, sravanreddy001
@shashank:
sorting the hashed values is more intensive than using the heap with size
K. (as kN)
sorting hash -- N log N
using heap -- N log k
also, i just read about the splay trees.. this can improve the performance
of 'N log N factor' right when used on input, though it can be used on a
@shashank: your approach fails for (2,0,0,0) (1,1,1,1)
but.. from any of the above approaches seen, we couldn't be 100% sure of
the solution,
but, from shashank's approach, the probability of finding correct soultion
can be improved by using some random prime numbers.
(running tests for more
Since A uses the MFU (most frequently used) to remove from memory, the
number used twice will not be in memory and never called for.
Mostly likely that A will win. (cannot say this 100% sure, though i don't
see a situation where S wins)
initial guess will be when any 5 numbers are repeated
any comments of the following approach.
first sort the weights,
find the 'j' such that sum( wts from w1 until wj) Wmax sum( wts from W1
until Wj+1) Wmax
also 'k' such that sum(wts from Wk to Wn) Wmax sum(wts from Wk-1 to Wn)
Wmax
so, a = j ( is the max number of elements in any subset,)
Sorry for being offtopic but yes if anyone proposes a polynomial time
algorithm(which can work for all cases) he is entitled to a prize money of
1 million. http://en.wikipedia.org/wiki/Millennium_Prize_Problems
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
@atul..
The table is used to record the state of subsets not print them.. (I
am assuming that's what u meant)..Hence keeping that in mind, yes it
captures all subsets... Now once A[N, K] is 1 that means there are
some subsets whose sum will be equal to K. Hence, to find all such
subsets we will
my question is about how to achieve digitization of an image/graph image.
for example i have the following ECG image( taken from a normal camera ):-
http://i.stack.imgur.com/QAMfk.png
so what algorithm should i follow to get the digitized image, my final aim
is to feed this information to a
Hi
Can any1 suggest a algo for heaviest increasing subsequence of a given
array?
(HIS is the LIS when weights are included for each element in the
array)
Thanks in advance
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
24 matches
Mail list logo
