Which college?
On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote:
Google is visiting our campus 4 different roles As of now IT field
technician is confirmed so how to approach 4 written test. ??
--
You received this message because you are subscribed to the
JVC is a multi-part algorithm which consists of a shortest augmenting
path algorithm (JV) followed by a modified auction algorithm (C). It
is best implemented as a sparse matrix. JVC is definitely an example
of efficiency requiring a significant increase in complexity. The code
implementing JVC is
@Gene: if all matrices are of N x N , and my size of L1 cache is L1, then
If I need a block of A and B to fit in cache would I need it as 2 x
(blocksize )^2 x 8 ( bytes per data item-for example) = L1 ?? or would I
need it as 3 ( including C block ) x (blocksize)^2 x 8 = L1 ? Am confused.
I tried
I want insertion , deletion, find (any general element) and min_element -
all 4 operations in constant time order.
Is there any data structure that can help me do this?
- Sehaj
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
I want constant time sort, but I can't have that either.
Don
On Mar 5, 3:27 pm, Sehaj Singh Kalra sehaj...@gmail.com wrote:
I want insertion , deletion, find (any general element) and min_element -
all 4 operations in constant time order.
Is there any data structure that can help me do this?
Use two stack :-
One stack is used for inserting and deleting the elements in the stack ,
supposing the the addition and deletion is done at the end of the stack .
So it will be of in constant time .
The Second Stack is used keeping track of the smallest number .
For finding the element we
@SAMM : Nice way to keep the track of the smallest number. But by your way
we won't be able to do search in constant time.
@Don : I was asked this question during an interview, so I think there
must/might be some possible solution.
On Tue, Mar 6, 2012 at 3:55 AM, SAMM somnath.nit...@gmail.com
As I mentioned we have to use hashing using Separate Chaning to find the
element in constant time . This is different than than opening addresing
which added the element to the next free slot in case of a collision , so
we cann't keep track of the element in a constant . In sepate Chaning the
Ok. Got it. I think that without the assumption that you took ( about FIFO
implementation i.e. only the recent most element to be added can be deleted
or else there would be problem in updating stack 2) the problem can't be
done. Thanks for the proposed solution.
On Tue, Mar 6, 2012 at 4:13 AM,
What Don so succinctly said is this: Comparison sort _requires_ O(n
log n) comparisons. If you had the data structure you're asking for,
you could easily implement a comparison sort: Just insert n items,
then then repeat n times: find min and delete that min. With your
proposed time bounds, the
You can get an initial guess with math. The rest you'll need to
determine by experiment. The math will be
Block Dimension = sqrt( L1 / sizeof(FLOAT) / K ) .
K could be 2 or 3 depending on the loop order. A reason you can't
predict perfectly is that interrupt handlers can add to cache load in
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
This is what the code is computing. A basic number
could you refer a number theory book..?
On Tue, Mar 6, 2012 at 7:01 AM, Gene gene.ress...@gmail.com wrote:
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic
Here is the nice link for writing fast matrix-matrix multiplication.
http://spiral.ece.cmu.edu:8080/pub-spiral/abstract.jsp?id=100
Apart from this we can vectorize the code and also we can do
unrolling to get very good performance.
--
With love and regards,
Sairam Ravu
I M.Tech(CS)
Sri
14 matches
Mail list logo
