You can't make it deterministically run in O(nlogn).
On Wed, Jan 5, 2011 at 1:25 PM, lee steath...@gmail.com wrote:
how can we make quick sort to run in O(logn) time in worst case??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
If we modify the PARTITION to use SELECT algorithm given in clrs to find
median and partition the array about it, then i think it will be O(nlogn)
worst case, because the array will be perfectly divided into 2 equal size
arrays each time. But is the practical implementation of SELECT that fast?
1-D simple dp with state current index you are at
On Wed, Jan 5, 2011 at 7:41 AM, Akash Agrawal akash.agrawa...@gmail.comwrote:
didn't get the question correct...
Can u cite an example...
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Wed, Jan 5, 2011 at 12:36 AM, Decipher
Space complexity is O(N^2), but time complexity will be O(N^3 log K) - this
is too slow.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
There is a killer-case for the quicksort algorithm on which it runs in a
quadratic time.
However, before running sorting algorithm we can randomly shuffle the array,
so time will be reduced to the expected.
--
You received this message because you are subscribed to the Google Groups
Right. It can be solved simply in O(n^2). To optimize use segment trees.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Can you elaborate how to put segment tree into picture
On Wed, Jan 5, 2011 at 2:57 PM, juver++ avpostni...@gmail.com wrote:
Right. It can be solved simply in O(n^2). To optimize use segment trees.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
dp[i] - profit from the opening restaurants up to the i-th position.
dp[i] = max(dp[i - 1], p[i] + max[dp[j], j = A and distance between i and
j at least k]).
Segment trees are helpful to find maximum profir for the positions to th
elft of the current.
So we use tree of maximums. To satisfy
dangling pointers ?? maybe.. also corrupted heap
On Wed, Jan 5, 2011 at 4:46 PM, bittu shashank7andr...@gmail.com wrote:
You are given a the source to a application which is crashing when
run. After running it 10 times in a debugger, you find it never
crashes in the same place. The
Corrupted stack - buffer overflow.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
You have a stream of infinite queries (ie: real time Google search
queries that people are entering). Describe how you would go about
finding a good estimate of 1000 samples from this never ending set of
data and then write code for it.
--
You received this message because you are subscribed to
using randomized version of quick sort time complexity even in the
worst case is o(nlogn)
Regards
priyaranjan
code-forum.blogspot.com
On Jan 5, 12:55 pm, lee steath...@gmail.com wrote:
how can we make quick sort to run in O(logn) time in worst case??
--
You received this message because you
selecting pivot as a near median using order stastics method(O(n)) we can
run it in worst case O(nlogn)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this
@MAC
ur solution is wrong
1 9 24
2 12 33
3 16 49
search for 3
O(logn) solution
let the matrix be A[][] and number to be searched is x
divide the array from middle in 4 parts lets say it four quadrants
now check if xA[n/2][n/2] search in bottom right quadrant
if xA[n/2][n/2] search in other 3
I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise
in others.
On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.comwrote:
aditya solution is correct
it is a standard question of young tabuleau
it is complexity is log(n)
On Wed, Jan 5, 2011 at 6:52
@ankit thanks for correcting
@naveen yeah that will make it more precise
On Wed, Jan 5, 2011 at 7:51 PM, Ankit Babbar ankitbabba...@gmail.comwrote:
@ Aditya: Mac's Solution works correctlyfor your example:
Start from 24(top right)..245: go left;95: go left; 13: go
down; 23:go
There might be some error in calculating the value of some variable(s) which
might be used to retrieve elements in some arrays/maintaining stack/linked
list or any other data structure that uses the value of that variable to
retrieve information from memory.
Carefully checking the values of
Hi ,
i m getting error can u find the error in code for following problem??
We will use the following (standard) definitions from graph theory. Let V be
a nonempty and finite set, its elements being called vertices (or nodes).
Let E be a subset of the Cartesian product V×V, its elements being
only 2 stacks, one of them (or both...) should provide functionality for
retrieving minimum.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
I think your solution will take O(n3) time , as it will require three
loops . 1st for index i , 2nd for first max and 3rd for second max .
Instead we should take :
dp[i] = max(dp[j]) + p[i] , where ji and m[i] - m[j] k . Pls
correct me if something is wrong .
--
You received this message
We are given a checkerboard which has 4 rows and n columns, and has an
integer written in each square. We are also given a set of 2n pebbles,
and we want to place some or all of these on the checkerboard (each
pebble can be placed on exactly one square) so as to maximize the sum
of the integers in
Good point. Right.
But we can avoid first stack of such structure, having separate variable
(Minimum) for this.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
Either x is greater or less than the middle vale you have to search 3
quardant. Because the value could be in bottom left or top tight.
On Jan 5, 2011 7:14 AM, ADITYA KUMAR aditya...@gmail.com wrote:
@ankit thanks for correcting
@naveen yeah that will make it more precise
On Wed, Jan 5, 2011
int solve(int id) {
if(id==n)
return 0;
int d = dp[id];
if(~d) return d;
d = 0;
for(int i=id+1;in;i++) {
if(dis[i]-dis[id]=k) {
d ?= val[id] + solve(i);
}
}
return d;
}
Its O(n^2), and Juver++, is very
Unfortunately, you are wrong.
We need one loop for i and that is all. All other things for searching max
p[j] is solved by segment tree in O(log n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
I am telling the DP O(n^2) solution, whts wrong in it??
On Wed, Jan 5, 2011 at 10:36 PM, juver++ avpostni...@gmail.com wrote:
Unfortunately, you are wrong.
We need one loop for i and that is all. All other things for searching max
p[j] is solved by segment tree in O(log n).
--
You received
Other useful information about this structure is
herehttp://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
I was replying to the @Decipher post. Not yours. :)
Your algorithm seems to be ok.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
ok :):)
On Wed, Jan 5, 2011 at 10:43 PM, juver++ avpostni...@gmail.com wrote:
I was replying to the @Decipher post. Not yours. :)
Your algorithm seems to be ok.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
Minor fixes:
i loop should be from 0 to id - 1, if you are moving from left to right.
initial value of d should be the val[id] not 0.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Sorry, disregard my first proposition about index i.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
In main just pass
answerIs = max(val[0], solve(0));
On Wed, Jan 5, 2011 at 10:49 PM, juver++ avpostni...@gmail.com wrote:
Sorry, disregard my first proposition about index i.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
That's a big save of space!
On Jan 5, 2011 9:03 AM, juver++ avpostni...@gmail.com wrote:
Good point. Right.
But we can avoid first stack of such structure, having separate variable
(Minimum) for this.
--
You received this message because you are subscribed to the Google Groups
Algorithm
In any column, we can place atmost 2 pebbles.
(a) Considering an isolated column, we can place 1 or 2 pebbles.
Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4}
(b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum
that can be achieved starting from column 'i' to column 'n-1' (columns
This is correct. It ensures there can be no degenerate partitions and
improves the worse case run time to be asymptotically equal to the average
case.
In practice you would want to use a simple pivot selection algorithm and
only resort to SELECT when the simple algorithm fails to produce a
Thanks everyone for suggestions and follow my Dynamic Programming -
Series for more questions on DP .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this
36 matches
Mail list logo
