Re: [algogeeks] Re: Algorithm page

http://translate.google.com.br/translate?sl=pt&tl=en&js=n&prev=_t&hl=pt-BR&ie=UTF-8&u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F08%2Fjosephus-problem.html http://translate.google.com.br/translate?hl=pt-BR&sl=pt&tl=en&u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F08%2Flinks-da-sema

[algogeeks] Re: algorithm to sort based on frequency.

I have not tested this, but it should get you started: struct item { int val; int freq; int index; }; // Compare function for qsort. // Returns 1 if a occurs with greater frequency than b // Returns -1 if b occurs with greater frequency than a // Otherwise returns 1 if a is encountered b

Re: [algogeeks] Re: algorithm to sort based on frequency.

Can anyone give me example using hash+linked list method ..although i got dave method.but still... On Tue, Apr 16, 2013 at 8:58 PM, Dave wrote: > @Varun: Here is an algorithm using sorting only: > > 1. Append an index onto each number, so your example becomes {{4,0}, > {3,1}, {2,2}, etc.} > > 2

[algogeeks] Re: algorithm to sort based on frequency.

@Varun: Here is an algorithm using sorting only: 1. Append an index onto each number, so your example becomes {{4,0}, {3,1}, {2,2}, etc.} 2. Sort the numbers and their associated indices into ascending order by number. Your example becomes {{2,2}, {2,6}, {3,1}, {4,0}, {4,4}, etc.}. If the so

Re: [algogeeks] Re: algorithm to sort based on frequency.

@don.can u plz explain with example. On Wed, Feb 1, 2012 at 9:29 PM, Don wrote: > Build a hashmap with the array value as a key mapping to a struct > which contains the key, frequency, and location of first occurance. > Then sort the hashed elements comparing first by frequency and > breaking t

Re: [algogeeks] Re: Algorithm page

http://translate.google.com.br/translate?hl=pt-BR&sl=pt&tl=en&u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F03%2Fusando-busca-binaria-ensinando-pescar.html Wladimir Araujo Tavares *Federal University of Ceará Homepage | Marat

Re: [algogeeks] Re: Algorithm page

http://marathoncode.blogspot.com.br/2013/01/representacao-do-ponto-flutuante-em.html http://marathoncode.blogspot.com.br/2013/01/soma-de-subconjunto-subset-sum.html http://marathoncode.blogspot.com.br/2013/01/conjuntos-disjuntos.html Wladimir Araujo Tavares *Federal University of Ceará

Re: [algogeeks] Re: Algorithm page

Exception C http://translate.google.com.br/translate?sl=pt&tl=en&js=n&prev=_t&hl=pt-BR&ie=UTF-8&layout=2&eotf=1&u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F11%2Fexcecoes-em-c.html Wladimir Araujo Tavares *Federal University of Ceará Homepage

Re: [algogeeks] Re: Algorithm page

Simple problems on graphs http://translate.google.com.br/translate?sl=pt&tl=en&js=n&prev=_t&hl=pt-BR&ie=UTF-8&layout=2&eotf=1&u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html Wladimir Araujo Tavares *Federal University of Ceará Homepage

Re: [algogeeks] Re: Algorithm page

http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane.html http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane-2d.html http://marathoncode.blogspot.com.br/2012/08/as-proximas-cinco-linguagens-para-voce.html Wladimir Araujo Tavares *Federal University of Ceará

Re: [algogeeks] Re: Algorithm page

http://marathoncode.blogspot.com.br/2012/08/ano-turing.html http://marathoncode.blogspot.com.br/2012/08/logaritmo-discreto.html http://marathoncode.blogspot.com.br/2012/08/registrador-de-deslocamento.html http://marathoncode.blogspot.com.br/2012/08/paradoxo-do-aniversario.html http://marathoncode.b

Re: [algogeeks] Re: Algorithm page

http://marathoncode.blogspot.com.br/2012/08/truque-paridade-magica.html http://marathoncode.blogspot.com.br/2012/08/matematica-na-babilonia.html http://marathoncode.blogspot.com.br/2012/08/a-beleza-da-matematica.html http://marathoncode.blogspot.com.br/2012/08/jogo-das-cartas.html http://marathonco

Re: [algogeeks] Re: Algorithm page

http://translate.google.com.br/translate?sl=pt&tl=en&js=n&prev=_t&hl=pt-BR&ie=UTF-8&layout=2&eotf=1&u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F07%2Fquebra-cabecas-indutivos.html http://translate.googleusercontent.com/translate_c?hl=pt-BR&ie=UTF8&prev=_t&rurl=translate.google.com.br&sl=p

Re: [algogeeks] Re: Algorithm page

http://marathoncode.blogspot.com.br/2012/06/quais-sao-os-principais-artigos-da.html http://marathoncode.blogspot.com.br/2012/06/metodo-de-multiplicacao-em-grid.html http://marathoncode.blogspot.com.br/2012/06/vetor-associativo.html Wladimir Araujo Tavares *Federal University of Ceará

Re: [algogeeks] Re: Algorithm page

More post: http://marathoncode.blogspot.com.br/2012/06/qual-e-o-melhor-comentario-no-codigo.html http://marathoncode.blogspot.com.br/2012/06/importancia-de-algoritmos-eficientes.html http://marathoncode.blogspot.com.br/2012/06/um-professor-em-minha-vida.html http://marathoncode.blogspot.com.br/201

Re: [algogeeks] Re: Algorithm page

More posts: http://marathoncode.blogspot.com.br/2012/04/list-comprehension-and-generator.html http://marathoncode.blogspot.com.br/2012/04/floating-point-arithmetic-with.html http://marathoncode.blogspot.com.br/2012/05/algoritmos-gulosos.html http://marathoncode.blogspot.com.br/2012/05/algoritmos-de

Re: [algogeeks] Re: Algorithm page

Great Job!! Wladimir Araujo Tavares *Federal University of Ceará Homepage | Maratona| * On Mon, Apr 16, 2012 at 2:34 PM, Praveen Kumar wrote: > > Here[0] is one of the post( > http

Re: [algogeeks] Re: Algorithm page

Here[0] is one of the post( http://marathoncode.blogspot.com.br/2012/03/alguns-truques-da-linguagem-c.html) by Wladimir in english [0]http://codewar.in/c-tricks-vectors-and-algorithm-in-stl/ -- Cheers -- You received this message because you are subscribed to the Google Groups "Algorithm Gee

Re: [algogeeks] Re: Algorithm page

@wladimir can u upsate the site in English??? -- 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 email to algogeeks+unsubscr...@googlegrou

Re: [algogeeks] Re: Algorithm page

Hi Wladimir, How can we access an english version? Thanks, Vaibhav On Thu, Apr 12, 2012 at 10:48 PM, Wladimir Tavares wrote: > New good posts: > > > http://marathoncode.blogspot.com.br/2012/03/list-comprehension-e-generator.html > > http://marathoncode.blogspot.com.br/2012/03/projeto-de-algorit

Re: [algogeeks] Re: Algorithm page

New good posts: http://marathoncode.blogspot.com.br/2012/03/list-comprehension-e-generator.html http://marathoncode.blogspot.com.br/2012/03/projeto-de-algoritmos-usando-inducao.html http://marathoncode.blogspot.com.br/2012/03/jogo-nim.html http://marathoncode.blogspot.com.br/2012/03/alguns-truques

Re: [algogeeks] Re: Algorithm page

@Wladimir, Nice articles. Thanks. Best Regards, Rahul. On Tue, Feb 14, 2012 at 5:05 AM, Wladimir Tavares wrote: > > Hi Guys, > > I transfer some text for this blog. > http://marathoncode.blogspot.com > > Some good posts: > http://marathoncode.blogspot.com/2012/01/rand8-usando-rand5.html > http:

[algogeeks] Re: Algorithm page

Hi Guys, I transfer some text for this blog. http://marathoncode.blogspot.com Some good posts: http://marathoncode.blogspot.com/2012/01/rand8-usando-rand5.html http://marathoncode.blogspot.com/2012/02/conhecimento-perigoso-parte-i.html http://marathoncode.blogspot.com/2012/02/metaprogramacao-x-sp

[algogeeks] Re: algorithm to sort based on frequency.

Build a hashmap with the array value as a key mapping to a struct which contains the key, frequency, and location of first occurance. Then sort the hashed elements comparing first by frequency and breaking ties based on first occurance. Then iterate through the sorted elements and fill in the array

Re: [algogeeks] Re: algorithm problem

@ankur, does this actually connects from start station to end station?? i think ur solution creates path which could be discontinuous, but we want end to end connected path surender On Sat, Sep 17, 2011 at 5:39 AM, Ankur Garg wrote: > Some typos in my solution :( > Use a Max heap.. > > first tak

Re: [algogeeks] Re: algorithm problem

Some typos in my solution :( Use a Max heap.. first take the first 10 stations and build a* Max *heap O(10)..Heap contains distance between 2 stations . Initial Heap will contain 10 *minimum *distances with maximum of those at the top . Now 11 th comes u compare with the root of the heap . If i

[algogeeks] Re: algorithm problem

@Pankaj: Let's number the stations from 0 to 101, where stations 0 and 101 are the end stations and stations 1 through 100 are the intermediate stations. Let a[i], i = 1, 2, ..., 100 be the distance of station i from station 0, and finally assume that the a's are increasing, i.e., that the stations

Re: [algogeeks] Re: algorithm problem

Use a Max heap.. first take the first 10 stations and build a min heap O(10)..Heap contains distance between 2 stations . Initial Heap will contain 10 min distances with highest at the top . Now 11 th comes u compare with the root of the heap . If its less than that than replace it with the top a

[algogeeks] Re: algorithm problem

All possible subsets of 10 elements is B(100,10), which is over 17 trillion. Not a great algorithm. You can do this by constructing sets S_0, S_1, S_2, ... S_10, S_11 of stations accessible from the start in 0,1,2,...10, 11 hops. The 11th is from the final station to the destination. It's simple t

[algogeeks] Re: Algorithm complexity

Check interpolation which is a substitute for binary search for a uniformly sorted array. It has complexity of this order. On Aug 3, 7:31 pm, Ajai Sathyan wrote: >  Can you suggest a sample program which has complexity O(log log n)? > > Regards > Ajai Sathyan -- You received this message becaus

[algogeeks] Re: Algorithm complexity

Thanks guys... On Aug 4, 12:15 am, raj kumar wrote: > Searching a node in a tree of string or integer arrays and then using binary > search withinn that node to retrive a particular value -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To p

Re: [algogeeks] Re: Algorithm complexity

lol.. nice one :D On Thu, Aug 4, 2011 at 12:30 AM, Don wrote: >n = log(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 algogeeks@googlegroups.com. To unsubscribe from this group, send ema

[algogeeks] Re: Algorithm complexity

int main() { double n; printf("Enter n:"); scanf("%lf", &n); while(n > 1.0) n = log(log(n)); return 0; } On Aug 3, 9:41 am, Ajai Sathyan wrote: > Can u suggest a program with complexity O( log log n ) ? -- You received this message because you are subscribed to the Google Groups

Re: [algogeeks] Re: Algorithm for dynamic resource allocation

yes, something like that. My approach would have been priority = high, weight = 4 (assume) priority = medium, weight = 2 priority = low, weight = 1 now from you example, lets say number of consumers: Priority| No of Consumers --- High | 8 M

[algogeeks] Re: Algorithm for dynamic resource allocation

Dinesh, something like Weight of Low = 0.2 (High) Medium = 0.3 (High) and calculate the W of High and assign resource to all H, M , L accordingly am i on ryt way ??? or is there any other proven method to address this problem ??? On May 5, 11:39 am, dinesh bansal wrote: > You

[algogeeks] Re: Algorithm for dynamic resource allocation

Algorithm is going to decide what amount of resource given to customer/ consumer based on priority. On May 5, 6:33 am, ADITYA KUMAR wrote: > how much resource each customer needs...?? > > > > > > > > > > On Wed, May 4, 2011 at 6:13 PM, LiveShell wrote: > > Hi all, > > > I am working on dynam

[algogeeks] Re: Algorithm to find whether any 3point on the same line

Dave, This sounds a bit like quibling. Nearly all computational geometry algorithms assume real coordinates. Floating point implementation is a separate problem. This is _algorithm_ geeks... ;-) Nonetheless, if the coordinates are rational, then you can choose A,B,C integer as I said. Exact h

[algogeeks] Re: Algorithm to find whether any 3point on the same line

@Gene: The problem is that the quantities A, B, and C are likely to be floating point numbers because the x and y coordinates of the points are floating point numbers. You probably are going to want to compare for equality to within a tolerance. You can do that if you sort the slopes, but how do yo

[algogeeks] Re: Algorithm to find whether any 3point on the same line

Hi guys. I still think you can do it in O(n^2) if you grant that a hash table is O(1). For each pair of points (there are n(n-1)/2 of them, which is O(n^2), find A, B and C such that , Ax + By + C = 0 and furthermore ensure that A^2 + B^2 = 1. (Alternately if you are using rational arithmetic,

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

@Dave I was wrong. It can't be done in O(n^2) time. The best we can do is sort each row like you suggested in your other post. That will still be O((n^2)logn). Thanks, - Ravindra On Sun, Oct 24, 2010 at 7:06 PM, Meng Yan wrote: > for the 3th step, > for i=1 to n >for j=i+1 to n >

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

for the 3th step, for i=1 to n for j=i+1 to n for k=j+1 to n compare A[i,j] and A[j,k] if A[i,j]==A[j,k] find i,j,k are collinear. so we should need O(n^3), is it right? On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel wrote: > Can be done in O(n^2) time using the slope as people

[algogeeks] Re: Algorithm to find whether any 3point on the same line

We can do the following in 2-D plane where the pints are given in the form of (x.y). For each selection of three points do the following: Find the area of the triangle of the three points. Let it be A. If A is zero then Print "Existence of Co-linear points" Break. This can be achieved in C(n,3)

[algogeeks] Re: Algorithm to find whether any 3point on the same line

@Ravindra: Can you explain the algorithm for step 3 in more detail? I don't yet see how you do it in O(n^2), since it seems to me that comparing one A[i,j] to all the A[j,k] is already O(n^2). What am I missing? Dave On Oct 24, 12:05 am, ravindra patel wrote: > Can be done in O(n^2) time using t

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

For duplicates, either we can sort or use a Hash Set at the cost of extra space. While traversing all the points for slope etc calculation, insert the point into hash set. If a point already exists, skip it. Like this, we are calculating the slope and keeping track of distinct points in a single pa

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

Can be done in O(n^2) time using the slope as people suggested above. 1- Sort the points in increasing order of x cord. O(nlogn) 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) - O(n^2) [Note that point i and j are sorted in increasing order of x] 3- find a pair of A[i,j] and

[algogeeks] Re: Algorithm to find whether any 3point on the same line

@Preetika: Then you have to look for duplicates in an array of n(n-1)/ 2 real numbers. I think this takes the complexity above O(n^2). Dave On Oct 23, 10:54 pm, preetika tyagi wrote: > You have to scan every pair of points only once to get the value of 'm' and > 'a', so the time complexity would

[algogeeks] Re: Algorithm to find whether any 3point on the same line

@Meng Yan: s is an array of real numbers, not integers, so perhaps a counting sort is not applicable. Dave On Oct 23, 10:51 pm, Meng Yan wrote: > Thank you! > By the way, to do the 'sort s(i+1:n)', if I use counting sort, I think it > should be better. > -

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

Thank you! By the way, to do the 'sort s(i+1:n)', if I use counting sort, I think it should be better. imax = 0 // location of longest string of duplicate slopes lmax = 0 // length of longest string of duplicate slopes smax = unde

[algogeeks] Re: Algorithm to find whether any 3point on the same line

I gave an O(n^2 log n) algorithm to find the maximal number of collinear points in a set is given in http://groups.google.com/group/algogeeks/msg/d329dda12b332dd1. A fairly simple modification could answer the question as to whether any three points are collinear. Dave On Oct 23, 6:31 pm, Meng Y

Re: [algogeeks] Re: Algorithm to determine the largest number of envelopes that can be nested inside one another.

@Divesh, Can you please check the method present in Art_of_Programming_Contest_SE_for_uva.pdf for LIS nlogn (nlogk, k is the size of longest increasing sequence) page number 129 ?. (1,2) (2,13) (5,10) (7,9)(9,1) In this case, longest sequence is of length two and possible solutions are below,

[algogeeks] Re: Algorithm to determine the largest number of envelopes that can be nested inside one another.

I really liked Rahul's formulation; is it possible to solve a similar problem of finding Minimum number of envelopes (may be to save some stamps) to send all the envelopes with the graph representation? Maybe by using maximum flow to solve "Minimum path cover in directed acyclic graph", or am I mis

[algogeeks] Re: Algorithm to determine the largest number of envelopes that can be nested inside one another.

One thing to note is that, this graph is a directed acyclic graph, since by definition there can be no edge from a smaller or equal sized envelope to a large one. In this setting it is possible to find the longest path, by a topological sort and dynamic programming in linear time O(V+E). Funny thou

[algogeeks] Re: Algorithm to determine the largest number of envelopes that can be nested inside one another.

@Sathaian Please explain "Then find the longest increasing sequence of yi's -> nlog(n) " how to find this...?? Ex. (1,2) (2,13) (5,10) (7,9)(9,1) xi are sorted what will be the algo.. next?? On Sep 29, 8:55 am, Sathaiah Dontula wrote: > I think we can do like this, > > 1. Sort all t

[algogeeks] Re: Algorithm to find all subsets of size K

Exactly. And so how to generate all bit patterns with only k 1's? This is the heart of the problem, which has not yet been solved. It would be very wasteful with n=10,000, k=2 to try all 2^1 bit patterns looking for the small number with only 2 bits set: 1 choose 2, which is only abut 2^26

Re: [algogeeks] Re: Algorithm to find all subsets of size K

Though the approach is correct, but I think it should say that Generate all bit strings of size n with k bits set. Where n is the number of elements in the set and k is the number of 1's in the string. On Sun, Aug 22, 2010 at 2:08 PM, R.ARAVINDH wrote: > @raj > > > really cool > > On Aug 22, 1:08

[algogeeks] Re: Algorithm to find all subsets of size K

@raj really cool On Aug 22, 1:08 pm, Raj N wrote: > Generate all binary strings of length k. For eg: S={1,2,3,4,5} generate all > binary strings of length 5. 0 represents that particular number is absent > and 1 for the presence of the number. > > > > On Fri, Aug 13, 2010 at 11:35 PM, asdf wro

[algogeeks] Re: algorithm

I posted a more complete solution but it seems to have disappeared. Set up 2 heaps Lo and Hi where Lo has the max at its root and Hi has the min. I.e., Lo is a max heap and Hi is a min heap. Also maintain a variable M. Establish the invariants: 1. N(Lo) = N(Hi) where N(H) is the number of eleme

Re: [algogeeks] Re: algorithm

Please check the DS Symmetric Min-Max Heap, the root node is empty in this DS, we can use of this and use the root always median. I think this will give the median with O(1) and insertion and deletion costs O(logN). Thanks & regards, Sathaiah Dontula On Tue, Aug 3, 2010 at 7:59 AM, Gene wrote:

[algogeeks] Re: algorithm

Can you please explain how keeping two heaps min heap and max heap help in finding median in O(1) time? Regards, Bujji On Aug 3, 7:29 am, Gene wrote: > This is a great solution. > > On Jul 28, 3:09 am, janak wrote: > > > > > How about keeping heap? > > Have two heaps 1. max heap and 2. min he

Re: [algogeeks] Re: algorithm

@bijju: you are correct. Here goes the code for it. *http://codepad.org/4UgNpOKH * On Mon, Aug 2, 2010 at 7:29 PM, Gene wrote: > This is a great solution. > > On Jul 28, 3:09 am, janak wrote: > > How about keeping heap? > > Have two heaps 1. max heap and 2. min heap > > keep them equal size al

[algogeeks] Re: algorithm

This is a great solution. On Jul 28, 3:09 am, janak wrote: > How about keeping heap? > Have two heaps 1. max heap and 2. min heap > keep them equal size all the time and shift top element from one to > other when required... > > > > On Wed, Jul 28, 2010 at 7:46 AM, Gene wrote: > > I think you ha

[algogeeks] Re: algorithm

Median can be computed in O(1) time after the element is inserted into existing DS. But inserting a new element in to the AVL takes O(log n) time. Overall it takes O(log n) time including inserting new element and median computation. Can median be computed in O(1) time on the fly? On Jul 28, 7:

[algogeeks] Re: algorithm

@Anand, It looks like your algorithm takes O(log N ) time. Repeatedly choosing one half or the other half. Similar to binary search. Please correct me if I am worng. -Thanks and regards, Bujji. On Jul 27, 12:29 am, Anand wrote: > * > * > > *Using partition Logic of Quick Sort

[algogeeks] Re: algorithm

@Debajyoti. There are 25 possible values of 5*rand5() + rand5(). The largest multiple of 7 not exceeding 25 is 3*7. Thus, I divide by 3. The largest number n such that n/3 = 7 is 23. This is where the 3 and 23 come from. You might google "rejection method" to find fuller descriptions of the theory

[algogeeks] Re: algorithm

@Sony. I took (2/3)*rand5() as if (2/3) was a double. Otherwise, (2/3)*rand5() = 0*rand5() = 0, which is not what you calculated when you wrote 2*(i/3) instead of (2/3)*i. And yes, the fact that the distribution is not uniform does matter, since we want the results to be uniform. Using your interp

Re: [algogeeks] Re: algorithm

why u have chosen that 23 ? why dividing by 3 ? don't understand the logic. Please explain so that it become understandable. On 7/31/10, Dave wrote: > Use the rejection method... > > int rand7() > { > int i; > do > i = 5 * rand5() + rand5() - 3; > while( i > 23 ); > return

Re: [algogeeks] Re: algorithm

Hi Dave, i just checked; int i; int j; for(i=1;i<6;i++) { j = 2*(i/3); printf("\n%d\n",j); } gives me output 0,0,2,2,2. and there was no 3; and since we are anyway generating "random" numbers would this difference in distribution really matter? On Sat, Jul 31, 2010 at 6:30 PM

[algogeeks] Re: algorithm

@Sony. No. Consider the following table: rand5() (2/3)*rand5() _ 10 21 32 42 53 Thus, (2/3)*rand5() is not uniformly distributed, nor is it in the range 0 to 2. Dave On Jul 31, 7:49 am, S

Re: [algogeeks] Re: algorithm

what about int i = rand5() + (2/3)*rand5(); won't this work? On Sat, Jul 31, 2010 at 5:46 PM, Dave wrote: > Use the rejection method... > > int rand7() > { >int i; >do >i = 5 * rand5() + rand5() - 3; >while( i > 23 ); >return i / 3; > } > > The loop assigns i a value b

[algogeeks] Re: algorithm

Use the rejection method... int rand7() { int i; do i = 5 * rand5() + rand5() - 3; while( i > 23 ); return i / 3; } The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with uniform probability, and then rejects any value of i > 23. Thus, after the loop, i has a

[algogeeks] Re: ALGORITHM

Can use a map to read the array and do map[arr[i]]=1. If there's a 1 already present print arr[i]. This method solves the problem in O(n) time and O(n) space complexity. On Jul 29, 2:56 am, Minotauraus wrote: > If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 - > sum of all el

Re: [algogeeks] Re: ALGORITHM

@above: but this may lead to overflow of the integer as you don't know what is "n". if the value of n is large then you can;t do this On Thu, Jul 29, 2010 at 3:26 AM, Minotauraus wrote: > If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 - > sum of all ele

Re: [algogeeks] Re: ALGORITHM

#include int main() { int a[] = { 10,5,6,8,1,10,8,7,9,9}; /* Assuming a[i] is in {i=1,N} */ int N = 10,index,j; int i; for (i = 0; i < N; i++) { index = a[i] % N; if (a[index] > N) { printf("Duplicate number is %d\n",a[i]%N);

Re: [algogeeks] Re: ALGORITHM

I think we can assume a perfect hashing to exist. [Please correct me if I am wrong] Implementing one, is a different issue. :)) Other than hashing, we can use BST or Heap. ~ O(klog(n)) On Thu, Jul 29, 2010 at 1:07 PM, sourav wrote: > @Shiv > > Collision is itself a wel known issue in hashing

[algogeeks] Re: ALGORITHM

@Shiv Collision is itself a wel known issue in hashing and much need to be done to avoid collision. When you say your appraoch is hash the numbers, how do u make sure without knowing the nature of the numbers that you can hash them without bringing ing collision of inequal items of the array? On

[algogeeks] Re: ALGORITHM

If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 - sum of all elements in the array. That'll require one less loop compared to XORing twice. -Minotauraus. On Jul 28, 8:51 am, Apoorve Mohan wrote: > Solution : > > 1. Find Xor of numbers from 1 to n-1. > > 2. Find Xor of the n

[algogeeks] Re: ALGORITHM

@akshay Does the array contain numbers in the range 1 to n? On Jul 28, 8:16 pm, akshay wrote: > An array of unsorted numbers n is given with one no.repeated once ie > n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google

Re: [algogeeks] Re: algorithm

How about keeping heap? Have two heaps 1. max heap and 2. min heap keep them equal size all the time and shift top element from one to other when required... On Wed, Jul 28, 2010 at 7:46 AM, Gene wrote: > I think you have confused the statement of this problem.  The "(in > sorted order)" commen

[algogeeks] Re: algorithm

I think you have confused the statement of this problem. The "(in sorted order)" comment makes no sense because a median is exactly one number. One number is always sorted. After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that

Re: [algogeeks] Re: algorithm

Please ignore my previus mail as there was some typo mistake. /** find the Middle element in the Array without sorting it. * This function uses a modified version of QuickSort, where we * only consider the one half of the array. * This is a recursive function where we look at some section of th

Re: [algogeeks] Re: algorithm

/** find the Middle element in the Array without sorting it. * This function uses a modified version of QuickSort, where we * only consider the one half of the array. * This is a recursive function where we look at some section of the array * (Concerned Array) at a time. * * @param low

[algogeeks] Re: algorithm

Given that the list is in sorted order. Let us assume that the list in the form of an array A[1...n]. Case 1: If n is odd. Then the median is A[(n+1)/2]. Set MEDIAN:=A[(n +1)/2. Case 2: If n is even. Then the median is (A[n/2]+ A[n/2 +1])/2. Set MEDIAN:=(A[n/2]+ A[n/2 +1])/2. Assuming that the ar

[algogeeks] Re: Algorithm Books/Sites

I found a great place to read/contribute algorithms/puzzles: http://en.wikibooks.org/wiki/Algorithms#Why_a_Wikibook_on_Algorithms.3F (Its a featured book on wikipedia too) I plan to contribute to this book as much as I can. Please try to post in this book and paste links here. In a short span, t

[algogeeks] Re: algorithm to draw a line

See en.wikipedia.org/wiki/Bresenham's_line_algorithm Dave On Jul 12, 7:38 pm, Anand wrote: > 2 coordinate points p(x,y)and q(x,y) are given and write an algorithm to > draw aline -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to t

Re: [algogeeks] Re: Algorithm intensive Please solve

Hi, I think we could model this problem as a constraint problem and then use Integer linear programming to solve the same. You can find the solution to a similar problem here. http://www.ee.ucla.edu/ee236a/lectures/intlp.pdf Regards On Wed, Feb 17, 2010 at 8:54 AM, Dan wrote: > distance b

[algogeeks] Re: Algorithm intensive Please solve

distance between two points, a & b = SQRT[ (xa-xb)^2 + (ya- yb)^2) ] Define d = the above distance squared = (xa-xb)^2 + (ya-yb)^2) d = xa^2 - 2*xa*xb + xb^2 + ya^2 - 2*ya*yb + yb^2 d = xa^2 - 2*xa*xb + xb^2 + ya^2 - 2*ya*yb + yb^2 d = ( xa^2 + xb^2 + ya^2 + yb^2 ) - 2*(

Re: [algogeeks] Re: Algorithm intensive Please solve

@all i think all the above approaches are greedy.. we need dynamic solution to this problem.. On Sat, Feb 13, 2010 at 11:42 AM, vikrant singh wrote: > @sachin : the problem is bit more complex , consider N be 2 , and > coordinates be (-2,0) (0,0) (1,0) (3,0). your solution( min value=1+5=6) > wo

Re: [algogeeks] Re: Algorithm intensive Please solve

@sachin : the problem is bit more complex , consider N be 2 , and coordinates be (-2,0) (0,0) (1,0) (3,0). your solution( min value=1+5=6) wont give the right answer(2+2=4). On Sat, Feb 13, 2010 at 6:07 PM, sachin wrote: > We can make a spanning tree for these 2N points and then find the > minim

[algogeeks] Re: Algorithm intensive Please solve

We can make a spanning tree for these 2N points and then find the minimum spanning tree keeping in mind that a node can only be considered in one edge and not more than once. This will give you the minimum total sum of all the pairs. You can use kruskal's min spanning tree algorithm to find the min

[algogeeks] Re: Algorithm intensive Please solve

I am thinkin like.. make a completely connected graph.. (connect all 2N points to each other)... then delete connections starting with ones with max distance between them... this should give the desired result On Feb 11, 11:20 pm, GentLeBoY wrote: > given 2N points in a plane. Pair up to obtain N

[algogeeks] Re: algorithm to find Anagrams

On Thu, Jan 22, 2009 at 11:16 AM, dinesh bansal wrote: > > Can anyone provide me a good program/algorithm to find all anagrams for a > given word. > Input string should be of variable length (max 26 char). Just printing is > not enough, > we need to store the output to a file or static memory som

[algogeeks] Re: Algorithm needed for optimizing a grid layout

On Oct 15, 3:32 am, moonlight <[EMAIL PROTECTED]> wrote: > I wanted to check if this algorithm would work for me, but apparently > it's kept secret. I searched through wiki, google, etc. but could not > find any resource in any programming language. Could anyone point me > to a good algorithm libr

[algogeeks] Re: Algorithm needed for optimizing a grid layout

I wanted to check if this algorithm would work for me, but apparently it's kept secret. I searched through wiki, google, etc. but could not find any resource in any programming language. Could anyone point me to a good algorithm library or something? Thanks. Art On Oct 9, 4:14 pm, Geoffrey Summe

[algogeeks] Re: Algorithm needed for optimizing a grid layout

On Oct 9, 4:00 am, moonlight <[EMAIL PROTECTED]> wrote: <*snip*> > Obviously, some input data may yield this not solvable, such as when > user defines imageMinSide smaller than the width of target area. > The algorithm should collect satisfying results and return the one > with the largest num

[algogeeks] Re: Algorithm and DS for generating valid words from bag of (15) letters

On Jun 26, 6:45 pm, "Mohammad Moghimi" <[EMAIL PROTECTED]> wrote: > What kind of search algorithm you've used? Well, I don't really know ;-) Basically I have generated datastructure on start of program, where every node has propertis SuccLetters (= all letters containded in subbranch of current

[algogeeks] Re: Algorithm and DS for generating valid words from bag of (15) letters

What kind of search algorithm you've used? On 6/26/08, dingo <[EMAIL PROTECTED]> wrote: > > > There are plenty of games on net, where You have fixed (randomly > generated) letters (let's say fifteen of them) and You have to make up > as many valid words You can. > > There are some constraints, li

[algogeeks] Re: Algorithm composition, combination or aggregation

Thank you very much for your answer. What you say seems to be right. I am not sure if terms are commonly used, but a professor ask us to think about it. Thank you again, Jorge On 27 mar, 05:43, Gene <[EMAIL PROTECTED]> wrote: > On Mar 26, 4:58 am, jorgeba <[EMAIL PROTECTED]> wrote: > > > Hello,

[algogeeks] Re: Algorithm composition, combination or aggregation

On Mar 26, 4:58 am, jorgeba <[EMAIL PROTECTED]> wrote: > Hello, > > I am writting to ask if you know the difference between algorithm > composition, algorithm combination and algorithm aggregation. > > For example, a weighted sum of algorithms I think that it is a > combination. > > But I can imag

[algogeeks] Re: Algorithm Question Help Please!!!

I think you are doing the same thing the Simplex method does. Sorry but the Simplex does it better :) because you are increasing and decreasing only by 1 hour at a step. On Mar 25, 3:18 pm, Ashesh <[EMAIL PROTECTED]> wrote: > The PDF containing the solution is > here:http://groups.google.com/gr

[algogeeks] Re: Algorithm Question Help Please!!!

The PDF containing the solution is here: http://groups.google.com/group/algogeeks/web/AlgorithmQuestionSolution.pdf On Mar 25, 8:36 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > Any chance I could get a copy of that as well? :) > > On Mar 21, 3:49 am, Ashesh <[EMAIL PROTECTED]> wrote: > >

  1   2   >