Re: [algogeeks] Re: Algorithm page
http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F08%2Fjosephus-problem.html http://translate.google.com.br/translate?hl=pt-BRsl=pttl=enu=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F08%2Flinks-da-semana-i.html google translate doesn't translate page with mathjax :( Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Mar 26, 2013 at 11:52 PM, Wladimir Tavares wladimir...@gmail.comwrote: http://translate.google.com.br/translate?hl=pt-BRsl=pttl=enu=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F03%2Fusando-busca-binaria-ensinando-pescar.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Thu, Jan 17, 2013 at 4:12 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 12:56 PM, Wladimir Tavares wladimir...@gmail.com wrote: Exception C http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F11%2Fexcecoes-em-c.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 8:32 AM, Wladimir Tavares wladimir...@gmail.com wrote: Simple problems on graphs http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Sep 11, 2012 at 10:15 AM, Wladimir Tavares wladimir...@gmail.com wrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares wladimir...@gmail.com wrote: 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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
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 dondod...@gmail.com 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 ties based on first occurance. Then iterate through the
sorted elements and fill in the array. All steps are O(n) except for
the sort, so the overall complexity is O(n*log n).
Don
On Feb 1, 2:58 am, Varun tewari.va...@gmail.com wrote:
I was asked this question sometime during an interview.
WE have an array of known length. The elements in array can be
repetitive.
now sort the array based on frequency of occurrence of each element in
array.
Eg: a= {4.3.2.5.4.6.2.6}
after sorting a={4,4,2,2,6,6,3,5}
4,2,6 all occurs twice, in this case retain the order in which they
appeared in original array.
I was able to give a solution using hashing the elements of the array to
a
new array, and if hash matches, incrementing the count, and then sort the
hash values. Later, re scan the array to retain the order in case
there's a
match in frequency of any two element.
Looking for better alternatives.
Please pour in.
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
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 dave_and_da...@juno.com 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. 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 sort is not stable, the indices on equal numbers may not be in order,
as I've shown here, but that doesn't matter. It will be taken care of in
the next step.
3. Scan the array, and collapse every sequence of adjacent entries with
equal numbers into one entry with the lowest index, and append the
frequency to the entry. Your example becomes {{2,2,2}, {3,1,1}, {4,0,2},
etc.}
4. Sort the array with frequency as the primary key and index as the
secondary key. You get {{4,0,2}, {2,2,2}, {6,5,2}, {3,1,1}, {5,1,3}}.
5. Reexpand the array by repeating each number according to its frequency,
giving {4,4,2,2,6,6,3,5}.
Dave
On Wednesday, February 1, 2012 2:58:43 AM UTC-6, Varun wrote:
I was asked this question sometime during an interview.
WE have an array of known length. The elements in array can be repetitive.
now sort the array based on frequency of occurrence of each element in
array.
Eg: a= {4.3.2.5.4.6.2.6}
after sorting a={4,4,2,2,6,6,3,5}
4,2,6 all occurs twice, in this case retain the order in which they
appeared in original array.
I was able to give a solution using hashing the elements of the array to
a new array, and if hash matches, incrementing the count, and then sort the
hash values. Later, re scan the array to retain the order in case there's a
match in frequency of any two element.
Looking for better alternatives.
Please pour in.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algorithm page
http://translate.google.com.br/translate?hl=pt-BRsl=pttl=enu=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F03%2Fusando-busca-binaria-ensinando-pescar.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Thu, Jan 17, 2013 at 4:12 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 12:56 PM, Wladimir Tavares wladimir...@gmail.comwrote: Exception C http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F11%2Fexcecoes-em-c.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 8:32 AM, Wladimir Tavares wladimir...@gmail.comwrote: Simple problems on graphs http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Sep 11, 2012 at 10:15 AM, Wladimir Tavares wladimir...@gmail.com wrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares wladimir...@gmail.com wrote: 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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 12:56 PM, Wladimir Tavares wladimir...@gmail.comwrote: Exception C http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F11%2Fexcecoes-em-c.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 8:32 AM, Wladimir Tavares wladimir...@gmail.comwrote: Simple problems on graphs http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Sep 11, 2012 at 10:15 AM, Wladimir Tavares wladimir...@gmail.com wrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares wladimir...@gmail.com wrote: 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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html --
Re: [algogeeks] Re: Algorithm page
Simple problems on graphs http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Sep 11, 2012 at 10:15 AM, Wladimir Tavares wladimir...@gmail.comwrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html --
Re: [algogeeks] Re: Algorithm page
Exception C http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F11%2Fexcecoes-em-c.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Nov 28, 2012 at 8:32 AM, Wladimir Tavares wladimir...@gmail.comwrote: Simple problems on graphs http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Sep 11, 2012 at 10:15 AM, Wladimir Tavares wladimir...@gmail.comwrote: 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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares wladimir...@gmail.com wrote: 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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html --
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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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.blogspot.com.br/2012/08/algoritmo-pollards-rho.html http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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://marathoncode.blogspot.com.br/2012/08/multiplicacao-egipcia.html http://marathoncode.blogspot.com.br/2012/08/6-problemas-logicos.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Jul 10, 2012 at 10:32 AM, Wladimir Tavares wladimir...@gmail.comwrote: http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F07%2Fquebra-cabecas-indutivos.html http://translate.googleusercontent.com/translate_c?hl=pt-BRie=UTF8prev=_trurl=translate.google.com.brsl=pttl=entwu=1u=http://marathoncode.blogspot.com.br/2012/07/pilha-umapilha-e-uma-das-varias.htmlusg=ALkJrhj059Lg0n3irAidNipyRDh7UpI4nA http://translate.googleusercontent.com/translate_c?hl=pt-BRie=UTF8prev=_trurl=translate.google.com.brsl=pttl=entwu=1u=http://marathoncode.blogspot.com.br/2012/07/3n1.htmlusg=ALkJrhglAJwrFEt5u5P2V8l8P6Ez3FHXBQ Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algorithm page
http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F07%2Fquebra-cabecas-indutivos.html http://translate.googleusercontent.com/translate_c?hl=pt-BRie=UTF8prev=_trurl=translate.google.com.brsl=pttl=entwu=1u=http://marathoncode.blogspot.com.br/2012/07/pilha-umapilha-e-uma-das-varias.htmlusg=ALkJrhj059Lg0n3irAidNipyRDh7UpI4nA http://translate.googleusercontent.com/translate_c?hl=pt-BRie=UTF8prev=_trurl=translate.google.com.brsl=pttl=entwu=1u=http://marathoncode.blogspot.com.br/2012/07/3n1.htmlusg=ALkJrhglAJwrFEt5u5P2V8l8P6Ez3FHXBQ Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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á http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Fri, Jun 8, 2012 at 12:43 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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/2012/06/o-amor-e-uma-falacia-ou-nao-ensine.html http://marathoncode.blogspot.com.br/2012/05/algoritmos-gulosos.html http://marathoncode.blogspot.com.br/2012/05/algoritmos-de-tentativa-e-erro.html http://marathoncode.blogspot.com.br/2012/05/introducao-ao-haskell.html http://marathoncode.blogspot.com.br/2012/05/metodos-de-ordenacao.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Sat, May 26, 2012 at 1:09 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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-tentativa-e-erro.html http://marathoncode.blogspot.com.br/2012/05/introducao-ao-haskell.html http://marathoncode.blogspot.com.br/2012/04/paralelismo-de-bits.html http://marathoncode.blogspot.com.br/2012/04/inverso-multiplicativo.html http://marathoncode.blogspot.com.br/2012/04/usando-pthread.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 7:34 PM, Wladimir Tavares wladimir...@gmail.comwrote: Great Job!! Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 2:34 PM, Praveen Kumar praveen97...@gmail.comwrote: 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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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/2012/06/o-amor-e-uma-falacia-ou-nao-ensine.html http://marathoncode.blogspot.com.br/2012/05/algoritmos-gulosos.html http://marathoncode.blogspot.com.br/2012/05/algoritmos-de-tentativa-e-erro.html http://marathoncode.blogspot.com.br/2012/05/introducao-ao-haskell.html http://marathoncode.blogspot.com.br/2012/05/metodos-de-ordenacao.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Sat, May 26, 2012 at 1:09 PM, Wladimir Tavares wladimir...@gmail.comwrote: 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-tentativa-e-erro.html http://marathoncode.blogspot.com.br/2012/05/introducao-ao-haskell.html http://marathoncode.blogspot.com.br/2012/04/paralelismo-de-bits.html http://marathoncode.blogspot.com.br/2012/04/inverso-multiplicativo.html http://marathoncode.blogspot.com.br/2012/04/usando-pthread.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 7:34 PM, Wladimir Tavares wladimir...@gmail.comwrote: Great Job!! Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 2:34 PM, Praveen Kumar praveen97...@gmail.comwrote: 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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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-tentativa-e-erro.html http://marathoncode.blogspot.com.br/2012/05/introducao-ao-haskell.html http://marathoncode.blogspot.com.br/2012/04/paralelismo-de-bits.html http://marathoncode.blogspot.com.br/2012/04/inverso-multiplicativo.html http://marathoncode.blogspot.com.br/2012/04/usando-pthread.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 7:34 PM, Wladimir Tavares wladimir...@gmail.comwrote: Great Job!! Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 2:34 PM, Praveen Kumar praveen97...@gmail.comwrote: 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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algorithm page
Great Job!! Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Mon, Apr 16, 2012 at 2:34 PM, Praveen Kumar praveen97...@gmail.comwrote: 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 Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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-da-linguagem-c.html http://marathoncode.blogspot.com.br/2012/02/criterio-de-divisibilidade-por-3.html http://marathoncode.blogspot.com.br/2012/02/calculo-do-numero-de-combinacoes.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Feb 14, 2012 at 5:12 AM, rahul rahulr...@gmail.com wrote: @Wladimir, Nice articles. Thanks. Best Regards, Rahul. On Tue, Feb 14, 2012 at 5:05 AM, Wladimir Tavares wladimir...@gmail.comwrote: 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-spoj.html http://marathoncode.blogspot.com/2012/02/tutorial-sobre-xor.html http://marathoncode.blogspot.com/2012/02/encontrar-o-menor-entre-dois-inteiros.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Oct 5, 2011 at 7:11 PM, Wladimir Tavares wladimir...@gmail.comwrote: Hi Guys, I created this page to place some materials on algorithms. Suggestions are welcome. https://sites.google.com/site/quixadamaratona/ Ps: The page is in Portuguese. Best wishes, * * -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 wladimir...@gmail.comwrote: 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-da-linguagem-c.html http://marathoncode.blogspot.com.br/2012/02/criterio-de-divisibilidade-por-3.html http://marathoncode.blogspot.com.br/2012/02/calculo-do-numero-de-combinacoes.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Tue, Feb 14, 2012 at 5:12 AM, rahul rahulr...@gmail.com wrote: @Wladimir, Nice articles. Thanks. Best Regards, Rahul. On Tue, Feb 14, 2012 at 5:05 AM, Wladimir Tavares wladimir...@gmail.comwrote: 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-spoj.html http://marathoncode.blogspot.com/2012/02/tutorial-sobre-xor.html http://marathoncode.blogspot.com/2012/02/encontrar-o-menor-entre-dois-inteiros.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Oct 5, 2011 at 7:11 PM, Wladimir Tavares wladimir...@gmail.comwrote: Hi Guys, I created this page to place some materials on algorithms. Suggestions are welcome. https://sites.google.com/site/quixadamaratona/ Ps: The page is in Portuguese. Best wishes, * * -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algorithm page
@Wladimir, Nice articles. Thanks. Best Regards, Rahul. On Tue, Feb 14, 2012 at 5:05 AM, Wladimir Tavares wladimir...@gmail.comwrote: 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-spoj.html http://marathoncode.blogspot.com/2012/02/tutorial-sobre-xor.html http://marathoncode.blogspot.com/2012/02/encontrar-o-menor-entre-dois-inteiros.html Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Wed, Oct 5, 2011 at 7:11 PM, Wladimir Tavares wladimir...@gmail.comwrote: Hi Guys, I created this page to place some materials on algorithms. Suggestions are welcome. https://sites.google.com/site/quixadamaratona/ Ps: The page is in Portuguese. Best wishes, * * -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 its less than that than replace it with the top and run heapify (O(log10) ) ..keep doing the same . In the end u have 10 stations with min distance between them Complexity O(10) + O(log(10)) = O(1) ..Comparision takes constant time So total complexity O(1) Regards Ankur On Sat, Sep 17, 2011 at 5:00 AM, Dave dave_and_da...@juno.com wrote: @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 are presented in order. We want to find i[1], i[2], ..., i[10] such that 0 = i[0] i[1] i[2] ... i[10] i[11] = 101. Given any x, 0 x = a[101] (the distance between the end stations), we can find the last station that is within x of station 0. Call this station i1. In other words, a[i1] = x but a[i1+1] x. Now find the last station that is within x of station i[1] and call it i[2]. Etc until you find the last station that is within x of station i10. If you get to station 101 in the process, the rest of the i's = 101. This can be done with a linear search in O(100), or using 10 binary searches in O(10 log 100). Now the problem is to find the smallest x such that I[11] = 101. We can do this with a binary search on x. Initialize xmin = a[101]/11 (that would have the 10 intermediate stations equally spaced) and xmax = a[101] and begin a loop. Let x = xmin + (xmax - xmin)/2. If x == xmin or x == xmax, break; xmax is the minimax distance between stations and i[1], ..., i[10] are the stations. Otherwise, calculate i[1] through i[11] as above. If i[11] 101, then x is too small, so set xmin = x and loop. If i[11] = 101, then x is too large, so set xmax = x and loop. Dave On Sep 16, 1:22 pm, pankaj kumar p9047551...@gmail.com wrote: You are given two end points ( consider them as two end stations at some distance ) there are 100 stations between these two . Now you need to build a train track between these two end points which includes only 10 stations and not more than that . Now the objective is to find such 10 stations such that the maximum distance between any two consecutive stations is minimum . mine solution is find all possible subset of 10 elements and answer is that subset for which sum (of distance between consecutive stations )is minimum.. is it correct or any other solution. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 ankurga...@gmail.com wrote: 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 its less than that than replace it with the top and run heapify (O(log10) ) ..keep doing the same . In the end u have 10 stations with min distance between them Complexity O(10) + O(log(10)) = O(1) ..Comparision takes constant time So total complexity O(1) Regards Ankur On Sat, Sep 17, 2011 at 5:00 AM, Dave dave_and_da...@juno.com wrote: @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 are presented in order. We want to find i[1], i[2], ..., i[10] such that 0 = i[0] i[1] i[2] ... i[10] i[11] = 101. Given any x, 0 x = a[101] (the distance between the end stations), we can find the last station that is within x of station 0. Call this station i1. In other words, a[i1] = x but a[i1+1] x. Now find the last station that is within x of station i[1] and call it i[2]. Etc until you find the last station that is within x of station i10. If you get to station 101 in the process, the rest of the i's = 101. This can be done with a linear search in O(100), or using 10 binary searches in O(10 log 100). Now the problem is to find the smallest x such that I[11] = 101. We can do this with a binary search on x. Initialize xmin = a[101]/11 (that would have the 10 intermediate stations equally spaced) and xmax = a[101] and begin a loop. Let x = xmin + (xmax - xmin)/2. If x == xmin or x == xmax, break; xmax is the minimax distance between stations and i[1], ..., i[10] are the stations. Otherwise, calculate i[1] through i[11] as above. If i[11] 101, then x is too small, so set xmin = x and loop. If i[11] = 101, then x is too large, so set xmax = x and loop. Dave On Sep 16, 1:22 pm, pankaj kumar p9047551...@gmail.com wrote: You are given two end points ( consider them as two end stations at some distance ) there are 100 stations between these two . Now you need to build a train track between these two end points which includes only 10 stations and not more than that . Now the objective is to find such 10 stations such that the maximum distance between any two consecutive stations is minimum . mine solution is find all possible subset of 10 elements and answer is that subset for which sum (of distance between consecutive stations )is minimum.. is it correct or any other solution. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algorithm complexity
lol.. nice one :D On Thu, Aug 4, 2011 at 12:30 AM, Don dondod...@gmail.com 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 Medium | 5 Low | 2 Calculate total weight = 8*4+5*2+2*1 = 44 Now assign resource based on priority: Priority = high, Resource = 4 * 100 / 44 Priority = medium, Resource = 2 * 100 / 44 Priority= low, Resource = 1 * 100 / 44 Hope it makes more clear. -Dinesh Bansal On Thu, May 5, 2011 at 12:28 PM, LiveShell livesh...@gmail.com wrote: 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 bansal...@gmail.com wrote: You can assign weight to all the consumers based on priority and then divide all the resource based on weight. On Wed, May 4, 2011 at 6:13 PM, LiveShell livesh...@gmail.com wrote: Hi all, I am working on dynamic resource allocation problem. I have set of Consumer and resource. Consumers are with priority (High, Medium, Low). Now I want to assign resource slice to each consumer based on priority and no of consumers. ie Priority| No of Consumers --- High | 8 Medium |5 Low |2 OR Priority| No of Consumers --- High | 1 Medium |2 Low |10 My assumption is resource is 100 % and how can I assign slice of resource to each Consumer based on priority. Can any body give me idea which algorithm I should use. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 ravindra.it...@gmail.comwrote: 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 A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @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 preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 mengyan.fu...@gmail.com wrote: 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 ravindra.it...@gmail.comwrote: 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 A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @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 preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
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 = undefined // value of slope for i = 1 to n-1 for j = i+1 to n s(j) = slope of the line through points i and j end for j // O(n) * sort s(i+1:n) // O(n log n) *** scan s(i+1:n-1) looking for the longest string of duplicates // O(n) On Sat, Oct 23, 2010 at 10:32 PM, Dave dave_and_da...@juno.com wrote: 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 Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @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 preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 pass. Then 3 collinear points can be detected. On Sat, Oct 23, 2010 at 10:05 PM, ravindra patel ravindra.it...@gmail.comwrote: 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 A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @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 preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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, (1, 2), (2, 13) (1, 2), (5, 10) (1, 2), (7, 9) Please let me know if does not work. Thanks, Sathaiah On Thu, Sep 30, 2010 at 2:20 PM, Gönenç Ercan gon...@gmail.com wrote: 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 missing a point? On Sep 30, 11:43 am, Gönenç Ercan gon...@gmail.com wrote: 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 though If it wasn't strictly smaller than finding the longest path would be NP-Complete. On Sep 28, 9:03 pm, Rahul Singal rahulsinga...@gmail.com wrote: A possible solution i can think is create a directed graph where each vertex is a envelope and edges are from a bigger envelope to smaller envelope ( one which can fit in bigger envelope ) . Now the problem is reduce to finding longest path in the graph . Regards Rahul -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 aravindhr...@gmail.com wrote:
@raj
really cool
On Aug 22, 1:08 pm, Raj N rajn...@gmail.com 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 gyanendra1...@gmail.com wrote:
Most efficient algorithm to find all subsets of size K??
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 gene.ress...@gmail.com wrote: This is a great solution. On Jul 28, 3:09 am, janak chandar...@gmail.com 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 gene.ress...@gmail.com wrote: 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 the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group athttp:// groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 gene.ress...@gmail.com wrote: This is a great solution. On Jul 28, 3:09 am, janak chandar...@gmail.com 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 gene.ress...@gmail.com wrote: 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 the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group athttp:// groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: algorithm
Hi Dave,
i just checked;
int i;
int j;
for(i=1;i6;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, Dave dave_and_da...@juno.com wrote:
@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, Sony Jose sonyj...@gmail.com wrote:
what about
int i = rand5() + (2/3)*rand5();
won't this work?
On Sat, Jul 31, 2010 at 5:46 PM, Dave dave_and_da...@juno.com 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 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 uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and
generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony- Hide quoted text -
- Show quoted text -
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 dave_and_da...@juno.com 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 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 uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 souravs...@gmail.com wrote: @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 Jul 28, 11:38 pm, Shiv ... shivsinha2...@gmail.com wrote: What if the number are not consecutive? My approach- Put the numbers in a hash till a collision occurs. On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan apoorvemo...@gmail.com wrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.com 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 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALGORITHM
#includestdio.h
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);
// break;
}
a[index] += N;
}
//restore the array
for (j = 0; j i; j++){
if (a[j] N a[j]%10 != 0){
a[j] %= N;
}else if(a[j] N a[j]%10 == 0){
a[j] = N;
}
printf(%d ,a[j]);
}
printf(\n);
return 1;
}
On Thu, Jul 29, 2010 at 7:46 PM, Shiv ... shivsinha2...@gmail.com wrote:
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 souravs...@gmail.com wrote:
@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 Jul 28, 11:38 pm, Shiv ... shivsinha2...@gmail.com wrote:
What if the number are not consecutive?
My approach-
Put the numbers in a hash till a collision occurs.
On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan
apoorvemo...@gmail.comwrote:
Solution :
1. Find Xor of numbers from 1 to n-1.
2. Find Xor of the numbers present in the array.
3. Xor the results from step 1 and 2 you will get the repeated number.
On Wed, Jul 28, 2010 at 8:46 PM, akshay
akshayrastogi2...@gmail.comwrote:
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
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longerUS Army
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 anike...@gmail.com wrote: 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 apoorvemo...@gmail.com wrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.com 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 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 gene.ress...@gmail.com wrote: 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 the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 = Loweset index of the Concerned Array
* @param high = Heighest index of the Concerned Array
* @param mid= The middle of the element in concerned array mid = (high-low)/2
*/
int findMedian(int *arr, int low, int high, int mid){
int pivot = low;
int l=low;
int h = high;
if(l=h){
while(lh){
while(arr[l]=arr[pivot]) l++;
while(arr[h]arr[pivot]) h--;
if(lh){
// Swapping the left and right
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
}
// Swapping the pivot with the high pointer
int temp = arr[pivot] ;
arr[pivot] = arr[h];
arr[h] = temp;
}
if(mid h){
return findElementAtRank(arr, low, h-1, mid);
}else if(rank h ){
return findElementAtRank(arr, h+1, high, mid);
}else{
return arr[h];
}
}
On Tue, Jul 27, 2010 at 12:15 PM, Avik Mitra tutai...@gmail.com wrote:
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 array accessing, the addition and division takes
O(1) time. The running time of the algorithm is O(1).
On Jul 26, 1:15 pm, Manjunath Manohar manjunath.n...@gmail.com
wrote:
@Anand...for better efficiency..we can find the pivot as a random
integer..for better worst case complexity..
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longerUS Army
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 the array
* (Concerned Array) at a time.
*
* @param low = Loweset index of the Concerned Array
* @param high = Heighest index of the Concerned Array
* @param mid= The middle of the element in concerned array mid = (high-low)/2
*/
int findMedian(int *arr, int low, int high, int mid){
int pivot = low;
int l=low;
int h = high;
if(l=h){
while(lh){
while(arr[l]=arr[pivot]) l++;
while(arr[h]arr[pivot]) h--;
if(lh){
// Swapping the left and right
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
}
// Swapping the pivot with the high pointer
int temp = arr[pivot] ;
arr[pivot] = arr[h];
arr[h] = temp;
}
if(mid h){
return findMedian(arr, low, h-1, mid);
}else if(rank h ){
return findMedian(arr, h+1, high, mid);
}else{
return arr[h];
}
On Tue, Jul 27, 2010 at 1:33 PM, Shafi Ahmad shafi.ah...@gmail.com wrote:
/** 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 = Loweset index of the Concerned Array
* @param high = Heighest index of the Concerned Array
* @param mid= The middle of the element in concerned array mid =
(high-low)/2
*/
int findMedian(int *arr, int low, int high, int mid){
int pivot = low;
int l=low;
int h = high;
if(l=h){
while(lh){
while(arr[l]=arr[pivot]) l++;
while(arr[h]arr[pivot]) h--;
if(lh){
// Swapping the left and right
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
}
// Swapping the pivot with the high pointer
int temp = arr[pivot] ;
arr[pivot] = arr[h];
arr[h] = temp;
}
if(mid h){
return findElementAtRank(arr, low, h-1, mid);
}else if(rank h ){
return findElementAtRank(arr, h+1, high, mid);
}else{
return arr[h];
}
}
On Tue, Jul 27, 2010 at 12:15 PM, Avik Mitra tutai...@gmail.com wrote:
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 array accessing, the addition and division takes
O(1) time. The running time of the algorithm is O(1).
On Jul 26, 1:15 pm, Manjunath Manohar manjunath.n...@gmail.com
wrote:
@Anand...for better efficiency..we can find the pivot as a random
integer..for better worst case complexity..
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longerUS
Army
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longerUS Army
--
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 options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 vikrantsing...@gmail.comwrote: @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 sachin_mi...@yahoo.co.in wrote: 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 minimum spanning tree because kruskal's method works by finding the least cost edges then proceeding towards the max cost edges. I hope it solves your problem. Regards, Sachin On Feb 12, 9:20 am, GentLeBoY vikrantsing...@gmail.com wrote: given 2N points in a plane. Pair up to obtain N distinct pairs such that total sum of paired distances is minimum. N can be atmost 50. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ankur Aggarwal Research internee Optical Zeitgeist Laboratory Institut National de la Recherche Scientifique (INRS) - ÉMT 800, de la Gauchetière Ouest, bureau 6900 Montréal, QC, H5A 1K6 CANADA E-mail: ankur.1...@gmail.com Web: www.zeitgeistlab.ca -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 sachin_mi...@yahoo.co.in wrote: 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 minimum spanning tree because kruskal's method works by finding the least cost edges then proceeding towards the max cost edges. I hope it solves your problem. Regards, Sachin On Feb 12, 9:20 am, GentLeBoY vikrantsing...@gmail.com wrote: given 2N points in a plane. Pair up to obtain N distinct pairs such that total sum of paired distances is minimum. N can be atmost 50. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
