Re: [algogeeks] Re: infix
@vivek: read again: ) = -1 ( = +1 Keep a sum of all these as u iterate. That should never be negative Plus check for these types (if you need correct arithmetic expressions as well *some operator followed by )* * or / after a ( () -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, Jun 11, 2010 at 12:07 PM, Vivek Sundararajan < s.vivek.ra...@gmail.com> wrote: > @Rohit > > Consider : (a+)b > > The above is not well formed! :) > > On 11 June 2010 11:58, Rohit Saraf wrote: > >> @BALARUKESH : >> What are you saying !! >> and Why would this not work >> >> As you start you get sum -1 at start itself. Hence you quit. >> The sum should be >0 always and 0 at last >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> On Fri, Jun 11, 2010 at 11:09 AM, BALARUKESH >> wrote: >> >>> The increment and decrement method wont work correctly for all >>> cases >>> Ex:- >>> ))a+b(( >>> This is not a well formed parenthesis... But satisfies the algorithm. >>> The better way is to use a stack... When u find a ' ( ' push it into >>> the stack and when u find a ' )' pop off the top element. Finally the >>> stack should be empty. If [stack has one or more ' ( ' ] or [the stack >>> is empty and exp is not empty] then it is not a well formed >>> parenthesis... >>> >>> -- >>> 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. >> > > > > -- > "Reduce, Reuse and Recycle" > Regards, > Vivek.S > > -- > 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: infix
@BALARUKESH : What are you saying !! and Why would this not work As you start you get sum -1 at start itself. Hence you quit. The sum should be >0 always and 0 at last -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, Jun 11, 2010 at 11:09 AM, BALARUKESH wrote: > The increment and decrement method wont work correctly for all > cases > Ex:- > ))a+b(( > This is not a well formed parenthesis... But satisfies the algorithm. > The better way is to use a stack... When u find a ' ( ' push it into > the stack and when u find a ' )' pop off the top element. Finally the > stack should be empty. If [stack has one or more ' ( ' ] or [the stack > is empty and exp is not empty] then it is not a well formed > parenthesis... > > -- > 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] c output
c 1 6,2 u might be expecting 5,1 if u are forgetting the newline character :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] infix
) = -1 ( = +1 Keep a sum of all these as u iterate. That should never be negative Plus check for these types (if you need correct arithmetic expressions as well some operator followed by ) * or / after a ( () -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: binary nos
write an efficient algo to compute no. of sequences of n binary digits that do not contain 2 1's in a row. eg 111 is invalid whereas 1001001 is valid. HERE the number of sequences comes to be a fibonacci number , precisely fib(n+2). So this prob is equivalent to finding fibonacci numbers -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh wrote: > @rohit: fibonacci sequence may be the answer to the prob, but I am curious > why? I haven't come across any such fib sequence property... > > On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf > wrote: > >> @junta : are fibonacci sequence is the answer of the prob, it is not used >> :D >> >> ------ >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf >> wrote: >> >>> @debajyoti: read the prob before posting >>> >>> -- >>> Rohit Saraf >>> Second Year Undergraduate, >>> Dept. of Computer Science and Engineering >>> IIT Bombay >>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>> >>> >>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma < >>> sarma.debajy...@gmail.com> wrote: >>> >>>> First 20 fibo no as follows with binary form >>>> 0 = 0 >>>> 1 = 1 >>>> 1 = 1 >>>> 2 = 10 >>>> 3 = 11 >>>> 5 = 101 >>>> 8 = 1000 >>>> 13 = 1101 >>>> 21 = 10101 >>>> 34 = 100010 >>>> 55 = 110111 >>>> 89 = 1011001 >>>> 144 = 1001 >>>> 233 = 11101001 >>>> 377 = 10001 >>>> 610 = 1001100010 >>>> 987 = 011011 >>>> 1597 = 1100001 >>>> 2584 = 10111000 >>>> 4181 = 101010101 >>>> >>>> Now please explain how fibo no is coming under consideration.Both kind >>>> of no is mixed here. >>>> >>>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf < >>>> rohit.kumar.sa...@gmail.com> wrote: >>>> >>>>> Fib comes because she wants the number of such sequences >>>>> >>>>> -- >>>>> -- >>>>> Rohit Saraf >>>>> Second Year Undergraduate, >>>>> Dept. of Computer Science and Engineering >>>>> IIT Bombay >>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> >>>>> -- >>>>> >>>>> 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. >>>> >>> >>> >> -- >> 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. > -- 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: binary nos
@junta : are fibonacci sequence is the answer of the prob, it is not used :D -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf wrote: > @debajyoti: read the prob before posting > > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > > > On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma > wrote: > >> First 20 fibo no as follows with binary form >> 0 = 0 >> 1 = 1 >> 1 = 1 >> 2 = 10 >> 3 = 11 >> 5 = 101 >> 8 = 1000 >> 13 = 1101 >> 21 = 10101 >> 34 = 100010 >> 55 = 110111 >> 89 = 1011001 >> 144 = 1001 >> 233 = 11101001 >> 377 = 10001 >> 610 = 1001100010 >> 987 = 011011 >> 1597 = 1100001 >> 2584 = 10111000 >> 4181 = 101010101 >> >> Now please explain how fibo no is coming under consideration.Both kind of >> no is mixed here. >> >> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf >> wrote: >> >>> Fib comes because she wants the number of such sequences >>> >>> -- >>> -- >>> Rohit Saraf >>> Second Year Undergraduate, >>> Dept. of Computer Science and Engineering >>> IIT Bombay >>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>> >>> -- >>> >>> 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. >> > > -- 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] Single ordered list
I had answered this question(of multiple lists) 2 or three days back. Go into the archive if u wanna see :P -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 6:52 PM, Raj N wrote: > But what if the same same problem is extended for multiple lists. As the > individual lists have already been sorted, is there any efficient way or any > other sorting algo which exploits this fact. > > > On Tue, Jun 8, 2010 at 10:56 PM, divya jain wrote: > >> merging as in merge sort. >> >> On 8 June 2010 19:59, Raj N wrote: >> >>> What is the most efficient way of combining 2 separate ordered list >>> into a single ordered list ? >>> >>> -- >>> 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. >> > > -- > 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: binary nos
@debajyoti: read the prob before posting -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma wrote: > First 20 fibo no as follows with binary form > 0 = 0 > 1 = 1 > 1 = 1 > 2 = 10 > 3 = 11 > 5 = 101 > 8 = 1000 > 13 = 1101 > 21 = 10101 > 34 = 100010 > 55 = 110111 > 89 = 1011001 > 144 = 1001 > 233 = 11101001 > 377 = 10001 > 610 = 1001100010 > 987 = 011011 > 1597 = 1100001 > 2584 = 10111000 > 4181 = 101010101 > > Now please explain how fibo no is coming under consideration.Both kind of > no is mixed here. > > On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf > wrote: > >> Fib comes because she wants the number of such sequences >> >> -- >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> -- >> >> 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. > -- 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: ds
which is just the recursive version of the abovementioned iterative solution. P.S. -Please remove this quoted text when you are composing -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: binary nos
Fib comes because she wants the number of such sequences -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: constraints satisfied?
Your time complexity is not O(c) but O(n^2) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: sorted 2-d array
@senthilnathan : very nice indeed -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] ds
Of course you should do it via swappings.. why would one think of anything else :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Jun 7, 2010 at 10:39 PM, vadivel selvaraj wrote: > Hi guys d soln z quite easy by swapping the variables.. > consider a1a2a3a4b1b2b3b4 > In the first iteration, swap (a2,b1),(a4,b3) giving a1b1a3b3a2b2a4b4 > In the second iteration, swap (a3b3,a2b2) which gives d soln... > a1b1a2b2a3b3a4b4... > > Any comments on dis?? > > > > > On Mon, Jun 7, 2010 at 1:51 PM, Raj N wrote: > >> @sain: But the question demands O(n) time >> >> On Mon, Jun 7, 2010 at 3:35 AM, Anand wrote: >> >>> Here is my approach is o(n). >>> http://codepad.org/YAFfZpxO >>> >>> <http://codepad.org/YAFfZpxO> >>> >>> On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar >>> wrote: >>> >>>> >>>> >>>> this is ques by adobe and they want inplace soln.. >>>> >>>> -- >>>> 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. >>> >> >> -- >> 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. >> > > > > -- > Simplicity is prerequisite for reliability. > – Edsger W. Dijkstra > > -- > 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: binary nos
getting fibonacci nos is trivial using matrix multiplication in almost constant time. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] constraints satisfied?
A simple solution : Use the union find data structure and add notes for x1...xn and the negation of all these. Every constraint makes one union. Finally check if for any i , xi and !xi are connected. It is worst case O(n lg n) for sure where n is the number of equations. Average case is much better. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] binary nos
So u want efficient algo for fibonacci numbers? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] circularly sorted array
You can do binary search for the largest element in log n trivially. And then you know the shift ! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] array question
No it will be O(n). -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 > -- 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: Largest even length palindrome in a string!!
but actually we need something better as per prob, cannot be done in O(n). so we need to think of something like O(n lg n) or O( n ^ 3/2) :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] One question on Heap sort
try running it on a data sample. only that can make it clear. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
This is almost the most basic dp. Read some of the examples from eva tardos. That would help. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] One question on Heap sort
Can u elaborate on the 2nd step. btw, did u understand my soln? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Largest even length palindrome in a string!!
Just read your code. It wont even work. Do you assume only one even length palindrome!? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Largest even length palindrome in a string!!
What makes you think it is O(n^3). I did not read the code one but divya's solution seems to be O(n^2) for worst case. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] divisible by 3
Still if u want the solution convert to string and sum up all characters. if sum is greater than 9 repeat else check if it is 3 6 or 9 -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] One question on Heap sort
Did not understand what u said but it is extremely straight forward Add all the arrays to the heap comparision being only from the first element. Now remove the root, take the first element of root array and reinsert the rest of the array. Just keep doin this. To save space you might want to avoid adding the whole array and just add some reqd pointers. But the algo remains the same. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] sorted 2-d array
See the first row and first column and count the negative entries. Also let k be the number of negatives in first row and l be in first column. now remove the first row and column and recurse on th the top left k x l matrix that remains assuming that top left is minimum and increases on going right or down. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: o/p
oh... why did u put %u. i did not even notice that :P -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr
Ok. so you have a list. Iterating over it is linear isn't it? Ahh... you will need a doubly linked list or an arraylist.does it solve ur prob? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 5, 2010 at 5:17 PM, Antony Vincent Pandian.S. wrote: > @Rohit I accept that tokenization is linear. But how do you say > iteration over tokens in the new list and printing in reverse order as > linear? > > On 6/5/10, Rohit Saraf wrote: > > Tokenization is done in linear time. Just save the words in an list (And > > what makes you think of non-linearity in tokenization!) > > And then iteration over the tokens is trivially linear. > > ------ > > Rohit Saraf > > Second Year Undergraduate, > > Dept. of Computer Science and Engineering > > IIT Bombay > > http://www.cse.iitb.ac.in/~rohitfeb14 > > > > > > On Sat, Jun 5, 2010 at 11:01 AM, Antony Vincent Pandian.S. < > > sant...@gmail.com> wrote: > > > >> @Shobhit > >> @Rohit > >> > >> Is it done it linear time?? I dont think so... > >> > >> On Sat, Jun 5, 2010 at 9:33 AM, Rohit Saraf > >> wrote: > >> > >>> Tokenize the string and print it reverse! > >>> > >>> -- > >>> -- > >>> Rohit Saraf > >>> Second Year Undergraduate, > >>> Dept. of Computer Science and Engineering > >>> IIT Bombay > >>> http://www.cse.iitb.ac.in/~rohitfeb14< > http://www.cse.iitb.ac.in/%7Erohitfeb14> > >>> > >>> -- > >>> 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. > >>> > >>> > >> > >> > >> -- > >> Luv, > >> S.Antony Vincent Pandian > >> > >> -- > >> 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. > > > > > > -- > Sent from my mobile device > > Luv, > S.Antony Vincent Pandian > > -- > 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] o/p
If you make it unsigned short int.. then it goes to 65535 on g++/gcc -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] dynamic vs greedy aproach
Greedy can be used to find one solution which has some special characteristics. It should be like - You are able to say that if for any instance of size k the greedy and the optimal solution match, then for any corresponding instance of size k+1, the greedy solution is atleast as good as optimal. Dynamic programming is a more general approach which is generally used when there is optimal substructure and has mostly found use in doing exponential looking problems in polynomial time. i hope u understood -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Quick short stack space reduction
Actually he means the case when you implement quicksort using stacks. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr
Tokenization is done in linear time. Just save the words in an list (And what makes you think of non-linearity in tokenization!) And then iteration over the tokens is trivially linear. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 5, 2010 at 11:01 AM, Antony Vincent Pandian.S. < sant...@gmail.com> wrote: > @Shobhit > @Rohit > > Is it done it linear time?? I dont think so... > > On Sat, Jun 5, 2010 at 9:33 AM, Rohit Saraf > wrote: > >> Tokenize the string and print it reverse! >> >> -- >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> -- >> 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. >> >> > > > -- > Luv, > S.Antony Vincent Pandian > > -- > 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]
Inplace in O(n) seems unlikely to me. Well you should still try! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
I mean what about the approach did you not understand. Do you know about DP? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
Exactly that's what you need to do. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr)
Have you posted the same question twice or i am feeling sleepy? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
What precisely did you not understand?? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr
Tokenize the string and print it reverse! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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]
Make a hashmap... Any problem doing that? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Quick short stack space reduction
if you "short" the larger one first, then the smaller one will be in the stack for a long time. Which is wasting stack space. Now stop "shorting" and start sorting ! :) ------ Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
Oh i am talking only about printing the total number of solutions... If you backtrack... Obviously it would not be polynomial -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
@jitendra: How can you say that no polynomial algo can be found. I think you are wrong. A simple memoized formulation will make this polynomial because of the optimal substructure.. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Check if 2 linked lists are identical
simple in place O(n lg n) solution. Choose a pivot in first array and partition it like in quicksort. Find the pivot in second array and partition. Now recurse on both halves. At any point if no of elements in array are not equal... Abort! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
why don't you make use of the optimal substructure. You can easily use the recurrence relation as DP @all : people don't just paste your code. Words are better than code -- 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] Removing extra parentheses in an infix string
So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
The previoys post has no meaning ... was sent by mistake On 6/3/10, Rohit Saraf wrote: > A*(B+C*D) > > -- > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
A*(B+C*D) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Can you solve this?
Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
@divya: but still haven't you seen Jagadish's example? It is a counterexample to your greedy approach. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: another google telephone interview question
m this group, send email to >>>> algogeeks+unsubscr...@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.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. >>> >> >> -- >> 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. > > -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: another google telephone interview question
Obviously it's not possible, because if k=n, then she has sorted a normal array in O(n) ! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: another google telephone interview question
Heap maintains the word and frequency count On 5/18/10, Terence wrote: > How do you maintain the heap? Could you explain in detail for the > following example: > 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) > > On 2010-5-17 22:38, Jagadish M wrote: >> The best algorithm I can think of is to maintain a heap of k elements. >> Takes O(n log k) time. >> Is anything told about the values of the keys? If the keys have values >> less than N, then it is possible to do >> what you say, i.e sort them in place. >> >> >> -Jagadish >> http://www.cse.iitb.ac.in/~jagadish >> >> >> On May 13, 7:06 pm, divya wrote: >> >>> This problem was asked in google phone interview. We have N element >>> array with k distinct keys(No relation between k& N given so assume >>> k>> What is the best method to sort this array without using any extra >>> memory? Please elaborate. >>> >>> -- >>> 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 >>> 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.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: another google telephone interview question
It cannot obviously be better than O(N + k log k).(This is the case when there is infinite memory to use). So with space constraint i guess O(N log k) is not bad. (which means I cannot think of anything better :P) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] partion of array
I was really not able to digest the greedy thing
Great example!!
On 5/17/10, Amir hossein Shahriari wrote:
> @divya : it's a greedy approach and again it's WRONG!
> your answer for {110,100,90,70,60,10 } would be:
> A = { 110, 70, 60 }
> B = { 100, 90 , 10 }
> the difference is 40
> the correct ans:
> A = { 110, 100 , 10 }
> B = { 90 , 70 , 60 }
> the difference is 0
> i don't believe a greedy algorithm would work for this problem!
>
> On Mon, May 17, 2010 at 5:06 PM, Rohit Saraf
> wrote:
>
>> @divya : descending order sorting works. BRILLIANT !!
>>
>> On 5/17/10, divya jain wrote:
>> > my algo on the array 1 200 500 2000
>> > sort the array therefore we have now 2000 500 200 1
>> > 1st array will have largest element
>> > A= {2000}
>> > and B={500}
>> > sumA=2000
>> > sumB=500
>> > now abs((2000+200)-500)>abs((2000)-(500+200))
>> > so we ll put 200 in array B. now since B has n/2 elements rest of the
>> > element goes to array which is 1.
>> > so the ans is
>> > A={2000,1}
>> > b={500,200}
>> >
>> >
>> > On 15 May 2010 19:10, Rohit Saraf wrote:
>> >
>> >> so what will ur algo give for array 1,200,500,2000
>> >>
>> >> On 5/15/10, divya jain wrote:
>> >> > my approach:
>> >> > 1. sort the array
>> >> > 2. take a variable diff. intitialize it to 0.
>> >> > 3. take the 1st element from array nd place it in array A and 2nd
>> >> > element
>> >> in
>> >> > array B. stoe in diff sum(A)-sum(B).
>> >> > 4. now place the next element in array A or B according to the
>> condition
>> >> if
>> >> >if sum(A+element)-sum(B)> sum(a)-sum(B+element). store the
>> >> > element
>> >> in
>> >> > B otherwise in A. also while storing the element in ny array
>> >> > maintain
>> >> the
>> >> > count of element in that aaray. if any time the count reaches n/2
>> where
>> >> > n
>> >> is
>> >> > the no. of elements in the given aaray. then store rest element in
>> the
>> >> > other array.
>> >> > 5. repeat step 5 until both array A n B get n/2 elements..
>> >> >
>> >> > hope my approach is clear and correct.
>> >> > comments are welcomed.
>> >> >
>> >> > On 15 May 2010 08:47, Rohit Saraf
>> wrote:
>> >> >
>> >> >> Choosing a greedy strategy for this would be difficult.
>> >> >>
>> >> >> For a simple dp you can
>> >> >> maintain A[i,total,present] using a recurrence
>> >> >>
>> >> >> i is the present index of array
>> >> >> total is the number of elements reqd in first partition.
>> >> >> present is the no of elements already there in first partition.
>> >> >>
>> >> >> the array stores difference between sums. GET the minimum of all
>> these
>> >> >> and backtrack.
>> >> >>
>> >> >>
>> >> >> On 5/15/10, Amir hossein Shahriari > >
>> >> >> wrote:
>> >> >> > @karas: your solution is greedy and its wrong e.g. for
>> >> >> > {1,2,3,4,5,100}
>> >> >> your
>> >> >> > diff would be 95 but the best result is 91
>> >> >> >
>> >> >> > i think we can solve this problem by dynamic programming but not a
>> >> >> > simple
>> >> >> > one! since the size of the two subsets must be equal.
>> >> >> > so it's DP solution has at least 3 dimensions: tow dimensions
>> >> >> representing
>> >> >> > the number of elements in each subset and another for the
>> difference
>> >> >> between
>> >> >> > their sums
>> >> >> >
>> >> >> > On Fri, May 14, 2010 at 10:11 PM, W Karas
>> wrote:
>> >> >> >
>> >> >> >> On May 14, 4:51 am, divya wrote:
>> >> >> >> > Algorithm to partition set of numbers into two s.t. diff bw
>> their
>> >> >> >> > sum is min and they hav equal num of elements
>> >> >> >>
>> >> >> >> void part(c
Re: [algogeeks] partion of array
@divya : descending order sorting works. BRILLIANT !!
On 5/17/10, divya jain wrote:
> my algo on the array 1 200 500 2000
> sort the array therefore we have now 2000 500 200 1
> 1st array will have largest element
> A= {2000}
> and B={500}
> sumA=2000
> sumB=500
> now abs((2000+200)-500)>abs((2000)-(500+200))
> so we ll put 200 in array B. now since B has n/2 elements rest of the
> element goes to array which is 1.
> so the ans is
> A={2000,1}
> b={500,200}
>
>
> On 15 May 2010 19:10, Rohit Saraf wrote:
>
>> so what will ur algo give for array 1,200,500,2000
>>
>> On 5/15/10, divya jain wrote:
>> > my approach:
>> > 1. sort the array
>> > 2. take a variable diff. intitialize it to 0.
>> > 3. take the 1st element from array nd place it in array A and 2nd
>> > element
>> in
>> > array B. stoe in diff sum(A)-sum(B).
>> > 4. now place the next element in array A or B according to the condition
>> if
>> >if sum(A+element)-sum(B)> sum(a)-sum(B+element). store the
>> > element
>> in
>> > B otherwise in A. also while storing the element in ny array maintain
>> the
>> > count of element in that aaray. if any time the count reaches n/2 where
>> > n
>> is
>> > the no. of elements in the given aaray. then store rest element in the
>> > other array.
>> > 5. repeat step 5 until both array A n B get n/2 elements..
>> >
>> > hope my approach is clear and correct.
>> > comments are welcomed.
>> >
>> > On 15 May 2010 08:47, Rohit Saraf wrote:
>> >
>> >> Choosing a greedy strategy for this would be difficult.
>> >>
>> >> For a simple dp you can
>> >> maintain A[i,total,present] using a recurrence
>> >>
>> >> i is the present index of array
>> >> total is the number of elements reqd in first partition.
>> >> present is the no of elements already there in first partition.
>> >>
>> >> the array stores difference between sums. GET the minimum of all these
>> >> and backtrack.
>> >>
>> >>
>> >> On 5/15/10, Amir hossein Shahriari
>> >> wrote:
>> >> > @karas: your solution is greedy and its wrong e.g. for
>> >> > {1,2,3,4,5,100}
>> >> your
>> >> > diff would be 95 but the best result is 91
>> >> >
>> >> > i think we can solve this problem by dynamic programming but not a
>> >> > simple
>> >> > one! since the size of the two subsets must be equal.
>> >> > so it's DP solution has at least 3 dimensions: tow dimensions
>> >> representing
>> >> > the number of elements in each subset and another for the difference
>> >> between
>> >> > their sums
>> >> >
>> >> > On Fri, May 14, 2010 at 10:11 PM, W Karas wrote:
>> >> >
>> >> >> On May 14, 4:51 am, divya wrote:
>> >> >> > Algorithm to partition set of numbers into two s.t. diff bw their
>> >> >> > sum is min and they hav equal num of elements
>> >> >>
>> >> >> void part(const int a[], int n_a, int g1[], int g2[])
>> >> >> {
>> >> >>int i, j, k;
>> >> >>
>> >> >>/* diff = sum(g1) - sum(g2) */
>> >> >>int diff;
>> >> >>
>> >> >>sort(a, n_a);
>> >> >>
>> >> >>diff = 0;
>> >> >>for (i = 0, j = 1, k = 0; j < n_a; ++k, i += 2, j += 2)
>> >> >> {
>> >> >>if ((a[i] > a[j]) == (diff > 0))
>> >> >> {
>> >> >>g1[k] = a[j];
>> >> >>g2[k] = a[i];
>> >> >> }
>> >> >>else
>> >> >> {
>> >> >>g1[k] = a[i];
>> >> >>g2[k] = a[j];
>> >> >> }
>> >> >>diff += g1[k] - g2[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...
Re: [algogeeks] Re: median of a bst
@Nikhil : For that size of subtrees at all nodes needs to be maintained. And in that case this is a trivial problem. @Sathaiah : See my solution :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] regarding DSW algortihm
Read it up : http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] question
@anurag : won't work -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] tree question
Either the root will be included or it will not be. If it's not, then it's equivalent to solving the problem on the subtrees. So let's consider the case when root node is included Now we keep track of A[node1,node2,reqdWeight] reqdWeight is the sum of wt reqd from paths starting from node1 and node2 Again, let's only see the case when we don't get a path of reqdWeight from one of the nodes alone. Then both node1 and node2 will be included. And i guess it's now a simple DP. @jalaj : i did not read your code but the topview shows that if it works, it is exponential. The algorithm I am suggesting will be polynomial. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] string question
@Navin: and that works ! :) @all : i am sure no heuristic/greedy strategy can be applied. @divya : did you check your array partitioning algorithm with my example ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] k the smallest in BST without using static variable
there is something called morris inorder traversal. credits to donald knuth On 5/15/10, kaushik sur wrote: > Hi Friends > > I have encountered the question in sites - "Given a Binary Search > Tree, write a program to print the kth smallest element without using > any static/global variable. You can't pass the value k to any function > also." > > I have tried my hands using explicit stack for inorder and keeping a > non-static count variable. > > I welcome any better solution, time and space efficient. > > Best Regards > Kaushik Sur > > -- > 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. > > -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
so what will ur algo give for array 1,200,500,2000
On 5/15/10, divya jain wrote:
> my approach:
> 1. sort the array
> 2. take a variable diff. intitialize it to 0.
> 3. take the 1st element from array nd place it in array A and 2nd element in
> array B. stoe in diff sum(A)-sum(B).
> 4. now place the next element in array A or B according to the condition if
>if sum(A+element)-sum(B)> sum(a)-sum(B+element). store the element in
> B otherwise in A. also while storing the element in ny array maintain the
> count of element in that aaray. if any time the count reaches n/2 where n is
> the no. of elements in the given aaray. then store rest element in the
> other array.
> 5. repeat step 5 until both array A n B get n/2 elements..
>
> hope my approach is clear and correct.
> comments are welcomed.
>
> On 15 May 2010 08:47, Rohit Saraf wrote:
>
>> Choosing a greedy strategy for this would be difficult.
>>
>> For a simple dp you can
>> maintain A[i,total,present] using a recurrence
>>
>> i is the present index of array
>> total is the number of elements reqd in first partition.
>> present is the no of elements already there in first partition.
>>
>> the array stores difference between sums. GET the minimum of all these
>> and backtrack.
>>
>>
>> On 5/15/10, Amir hossein Shahriari
>> wrote:
>> > @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100}
>> your
>> > diff would be 95 but the best result is 91
>> >
>> > i think we can solve this problem by dynamic programming but not a
>> > simple
>> > one! since the size of the two subsets must be equal.
>> > so it's DP solution has at least 3 dimensions: tow dimensions
>> representing
>> > the number of elements in each subset and another for the difference
>> between
>> > their sums
>> >
>> > On Fri, May 14, 2010 at 10:11 PM, W Karas wrote:
>> >
>> >> On May 14, 4:51 am, divya wrote:
>> >> > Algorithm to partition set of numbers into two s.t. diff bw their
>> >> > sum is min and they hav equal num of elements
>> >>
>> >> void part(const int a[], int n_a, int g1[], int g2[])
>> >> {
>> >>int i, j, k;
>> >>
>> >>/* diff = sum(g1) - sum(g2) */
>> >>int diff;
>> >>
>> >>sort(a, n_a);
>> >>
>> >>diff = 0;
>> >>for (i = 0, j = 1, k = 0; j < n_a; ++k, i += 2, j += 2)
>> >> {
>> >>if ((a[i] > a[j]) == (diff > 0))
>> >> {
>> >>g1[k] = a[j];
>> >>g2[k] = a[i];
>> >> }
>> >>else
>> >> {
>> >>g1[k] = a[i];
>> >>g2[k] = a[j];
>> >> }
>> >>diff += g1[k] - g2[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.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.
>> >
>> >
>>
>>
>> --
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>
>> --
>> 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.
>
>
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
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: partion of array
Choosing a greedy strategy for this would be difficult.
For a simple dp you can
maintain A[i,total,present] using a recurrence
i is the present index of array
total is the number of elements reqd in first partition.
present is the no of elements already there in first partition.
the array stores difference between sums. GET the minimum of all these
and backtrack.
On 5/15/10, Amir hossein Shahriari wrote:
> @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your
> diff would be 95 but the best result is 91
>
> i think we can solve this problem by dynamic programming but not a simple
> one! since the size of the two subsets must be equal.
> so it's DP solution has at least 3 dimensions: tow dimensions representing
> the number of elements in each subset and another for the difference between
> their sums
>
> On Fri, May 14, 2010 at 10:11 PM, W Karas wrote:
>
>> On May 14, 4:51 am, divya wrote:
>> > Algorithm to partition set of numbers into two s.t. diff bw their
>> > sum is min and they hav equal num of elements
>>
>> void part(const int a[], int n_a, int g1[], int g2[])
>> {
>>int i, j, k;
>>
>>/* diff = sum(g1) - sum(g2) */
>>int diff;
>>
>>sort(a, n_a);
>>
>>diff = 0;
>>for (i = 0, j = 1, k = 0; j < n_a; ++k, i += 2, j += 2)
>> {
>>if ((a[i] > a[j]) == (diff > 0))
>> {
>>g1[k] = a[j];
>>g2[k] = a[i];
>> }
>>else
>> {
>>g1[k] = a[i];
>>g2[k] = a[j];
>> }
>>diff += g1[k] - g2[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.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.
>
>
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
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] BST
hmmm i already realised that and even mailed that before :)
and if we want to use constant space do not make an array. the bst
itself is good enough to do what we are doing.
On 5/14/10, anna thomas wrote:
> @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum,
> then decrement the 2nd ptr(ptr at end of array)
> In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
> dec ptr2 1+4 = 5 (sum < 6)
> inc ptr2: 2+4 =6 (got the ans)
>
> But the qs mentions that it should be in O(1) space.
> Regards,
> Anna
>
>
>
> On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf
> wrote:
>
>> @divya : i guess... it wont work.
>> consider Array {1,2,3,4,123456}
>> and you want sum 6.
>>
>> @prashant: Is it O(n)?
>>
>> I guess after converting to array and removing all entries > sum, we
>> should
>> start with the smallest element
>> and scan the elements from last till we get some value x which together
>> with the smallest value sums to < sum. Call this position POS1.
>> If we get required sum somewhere in the process, cool !
>> Else take drop the elements after POS1 and also the smallest element.
>> Recurse on the remaining.
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>
>>
>>
>> On Fri, May 14, 2010 at 3:51 PM, Prashant K
>> wrote:
>>
>>> i think it can done like this,
>>> assume we have to find 'x' and 'y' wer s='x'+'y'
>>>
>>> 1) select ith node from tree (from beginning to end)
>>> 2) y= s - " ith number (node)"
>>> 3) now search for 'y' in BST if we found then there is node such that s=
>>> x
>>> + y; otherwise no..
>>>
>>> -- Prashant Kulkarni
>>> || Lokaha Samastaha Sukhino Bhavanthu ||
>>> || Sarve Jana Sukhino Bhavanthu ||
>>>
>>>
>>>
>>> On Fri, May 14, 2010 at 2:47 AM, divya jain
>>> wrote:
>>>
>>>> form a sorted array from inorder traversal of tree. now take to
>>>> pointers
>>>> one to the beginning of array and other at the end. now check if the sum
>>>> of
>>>> element is greater than reqd sum then increment 1st ptr. if their sum is
>>>> less than reqd sum then decrement 2nd ptr. if their sum is equal to the
>>>> reqd
>>>> sum then this is the ans..
>>>> hope it will work..
>>>>
>>>>
>>>> On 13 May 2010 20:11, jalaj jaiswal wrote:
>>>>
>>>>> given a bst... find two nodes whose sum is equal to a number k ... in
>>>>> O(n) time and constant space...
>>>>>
>>>>> --
>>>>> 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.
>>>>
>>>
>>> --
>>> 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 a
Re: [algogeeks] 2nd shortest path in a graph
I think... it will work :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 2:20 PM, divya wrote: > Given a graph's shortest path algorithm, how can you make use of it to > find the second shortest path? > > my solution > well just a thought... > is it something like.assume this is the smallest distance path > start->node1->node2->node3->node4->destination > (now the graph will be represented by a matrix of order 2) > in order start breaking any of the link(break only one) > eg:- break the link start->node(i.e. delete the entry in the matrix > which connects start and node1) > and then again use dijikras to find a distance(store it) > now again link the start node with the node1 and break the node1- > >node2 and find a distance... > after getting all the distances.find the min...that will be the > second min of all... > hope i am going on the right tracktell me if i am wrong...thanks > > -- > 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] partion of array
A simple DP should work. Should it not? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 4:15 PM, Sathaiah Dontula wrote: > Any assumption like, it has even number of elements and two distinct sets ? > > Thanks, > Sathaiah > > > > On Fri, May 14, 2010 at 2:21 PM, divya wrote: > >> Algorithm to partition set of numbers into two s.t. diff bw their >> sum is min and they hav equal num of elements >> >> -- >> 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. > -- 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] BST
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries > sum, we should
start with the smallest element
and scan the elements from last till we get some value x which together with
the smallest value sums to < sum. Call this position POS1.
If we get required sum somewhere in the process, cool !
Else take drop the elements after POS1 and also the smallest element.
Recurse on the remaining.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
On Fri, May 14, 2010 at 3:51 PM, Prashant K wrote:
> i think it can done like this,
> assume we have to find 'x' and 'y' wer s='x'+'y'
>
> 1) select ith node from tree (from beginning to end)
> 2) y= s - " ith number (node)"
> 3) now search for 'y' in BST if we found then there is node such that s= x
> + y; otherwise no..
>
> -- Prashant Kulkarni
> || Lokaha Samastaha Sukhino Bhavanthu ||
> || Sarve Jana Sukhino Bhavanthu ||
>
>
>
> On Fri, May 14, 2010 at 2:47 AM, divya jain wrote:
>
>> form a sorted array from inorder traversal of tree. now take to pointers
>> one to the beginning of array and other at the end. now check if the sum of
>> element is greater than reqd sum then increment 1st ptr. if their sum is
>> less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd
>> sum then this is the ans..
>> hope it will work..
>>
>>
>> On 13 May 2010 20:11, jalaj jaiswal wrote:
>>
>>> given a bst... find two nodes whose sum is equal to a number k ... in
>>> O(n) time and constant space...
>>>
>>> --
>>> 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.
>>
>
> --
> 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] compute kth smallest element from union of two lists
You have to take some i nodes from array A and the rest k-i-1 from array B. You do not know i. => Problem is to "Find i" So we do a binary search for that. The value i is acceptable if the (k-i) th element in B is greater than ith element in A. So, i guess you would have got it now. ------ Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] median of a bst
If you maintain the size of the subtree rooted at the nodes, then it will become easier. I guess you can see how. Else, 1) Use any algo to count the number of nodes in the BST.Let it be n. 2) Use morris inorder(no recursion/no stacks-all constraint met ) to traverse the tree. For each node visited increment the counter. a) If n is even then return avg(n/2,n/2+1)(counter == n/2) b) If n is odd return when counter == (n+1)/2(1-based indexing) You might want to read this up. : http://www.scss.tcd.ie/disciplines/software_systems/fmg/fmg_web/IFMSIG/winter2000/HughGibbonsSlides.pdf -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] compute kth smallest element from union of two lists
This was also asked in my Yahoo! Interview this year. :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 10:10 AM, Rohit Saraf wrote: > exactly .. > > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > > On Fri, May 14, 2010 at 10:07 AM, vignesh radhakrishnan < > rvignesh1...@gmail.com> wrote: > >> This is for kth largest. Change it for kth smallest >> >> In fact, this problem is amenable to something very similar to binary >> search. Suppose my arrays are A and B. The idea is to keep track of two >> indices, a (for A) and b (for B), such that a + b = k - 1 (it's very >> important to maintain this invariant). It's easy to check whether A[a] or >> B[b] is the answer: A[a] is the answer if and only if >> >> B[b-1] <= A[a] <= B[b], >> >> and B[b] is the answer if and only if >> >> A[a-1] <= B[b] <= A[a], >> >> where we use the convention that A[-1] = B[-1] = "negative infinity." >> (This can be determined in constant time.) Moreover, if neither of these is >> the case, you can divide the problem in half: if A[a] < B[b-1], you restrict >> your attention to the portion of A above index a and the portion of B below >> index b, and otherwise (it must be the case that B[b] < A[a-1]), you >> restrict your attention to the portion of A below index a and the portion of >> B above index b. (If you start with a and b in the middle of the arrays and >> always make the new indices be in the middle of the subarrays you're >> considering at that point, this step will always divide the problem in >> half.) >> Thanks to Lux Perpetua <http://forums.devshed.com/member.php?u=74699> >> source: >> >> http://forums.devshed.com/software-design-43/finding-kth-largest-element-in-a-union-of-two-arrays-137322.html >> >> >> On 13 May 2010 19:34, divya wrote: >> >>> You are given two sorted lists of size m and n. Give an O(log m+log n) >>> time algorithm for computing the kth smallest element in the union of >>> the two lists >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> There are two kinds of people. Those who care for others and The others >> >> -- >> 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] compute kth smallest element from union of two lists
exactly .. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 10:07 AM, vignesh radhakrishnan < rvignesh1...@gmail.com> wrote: > This is for kth largest. Change it for kth smallest > > In fact, this problem is amenable to something very similar to binary > search. Suppose my arrays are A and B. The idea is to keep track of two > indices, a (for A) and b (for B), such that a + b = k - 1 (it's very > important to maintain this invariant). It's easy to check whether A[a] or > B[b] is the answer: A[a] is the answer if and only if > > B[b-1] <= A[a] <= B[b], > > and B[b] is the answer if and only if > > A[a-1] <= B[b] <= A[a], > > where we use the convention that A[-1] = B[-1] = "negative infinity." (This > can be determined in constant time.) Moreover, if neither of these is the > case, you can divide the problem in half: if A[a] < B[b-1], you restrict > your attention to the portion of A above index a and the portion of B below > index b, and otherwise (it must be the case that B[b] < A[a-1]), you > restrict your attention to the portion of A below index a and the portion of > B above index b. (If you start with a and b in the middle of the arrays and > always make the new indices be in the middle of the subarrays you're > considering at that point, this step will always divide the problem in > half.) > Thanks to Lux Perpetua <http://forums.devshed.com/member.php?u=74699> > source: > > http://forums.devshed.com/software-design-43/finding-kth-largest-element-in-a-union-of-two-arrays-137322.html > > > On 13 May 2010 19:34, divya wrote: > >> You are given two sorted lists of size m and n. Give an O(log m+log n) >> time algorithm for computing the kth smallest element in the union of >> the two lists >> >> -- >> 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. >> >> > > > -- > There are two kinds of people. Those who care for others and The others > > -- > 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] tree from linked list
i guess the rotation solution i gave will take O(n) with the list as well (btw.. u can convert a list to array :P) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] tree from linked list
1) Make the middle element the root. Recursively make the left and right subtrees from the left and right halves of the link list. 2) Implement balanced insertion in trees (via rotations on every step...). Now insert each element -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, May 2, 2010 at 6:38 PM, divya wrote: > u are given a sorted lnked list construct a balanced binary search > tree from it. > > -- > 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] 400!
are forget abt representation. It can be stored as string anyways. Tail recursion is awesome at times ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, May 3, 2010 at 9:46 AM, siddharth srivastava wrote: > But is there any way to accomplish this without an array ? Even for 100!. > > > On 2 May 2010 06:15, Prasoon Mishra wrote: > >> I think challenge here is not the Execution time, but the storage. 300 ! >> or 400! should generally go beyond the storage capabilities of long long >> ints in cpp. >> @ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately >> be able to store the output. >> I think Rajesh Patidar's answer fits the bill well, in terms of storage. >> >> >> On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan < >> rvignesh1...@gmail.com> wrote: >> >>> I agree with abhijith. But given some very large x for which i would have >>> to find factorial. >>> I would either >>> (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an >>> interview >>> (ii) use simple brute multiplication algorithm. >>> The second approach requires >>> (a) The no. of digits in n! for making storage available >>> (b) The calculation itself which I would brute force >>> >>> References: >>> >>> http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html >>> >>> http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it >>> http://delphiforfun.org/programs/big_factorials.htm >>> >>> >>> >>> On 2 May 2010 13:59, Rohit Saraf wrote: >>> >>>> google it... u will gt it >>>> >>>> i am on mobile... cannot explain now.. >>>> >>>> On 5/2/10, divya jain wrote: >>>> > wat is tail recursion plz explan in detail >>>> > >>>> > On 2 May 2010 08:15, Rohit Saraf wrote: >>>> > >>>> >> @divya use tail recursion and rest should be fine.. >>>> >> >>>> >> -- >>>> >> -- >>>> >> Rohit Saraf >>>> >> Second Year Undergraduate, >>>> >> Dept. of Computer Science and Engineering >>>> >> IIT Bombay >>>> >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> <http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> >> >>>> >> -- >>>> >> 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. >>>> > >>>> > >>>> >>>> >>>> -- >>>> -- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> >>>> -- >>>> 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 >>>>
Re: [algogeeks] 400!
google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain wrote: > wat is tail recursion plz explan in detail > > On 2 May 2010 08:15, Rohit Saraf wrote: > >> @divya use tail recursion and rest should be fine.. >> >> -- >> ------ >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> -- >> 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. > > -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] 400!
@divya use tail recursion and rest should be fine.. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Finding the mode in a set of integers
Just got another O(n) solution. Find the n/2 th largest element in the array using the Median of Medians Selection algorithm. =? takes O(n) That's It ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Finding the mode in a set of integers
Remove as many 3's that would make it 1000. The example still holds @gauri: the logic is that if your pivot is greater than all numbers till middle then it would not effect the middle element. Hence if middle element is not the mode in the given array, the answerwould be wrong. On 4/15/10, vivek bijlwan wrote: > @rohit : thats more than 1000 elements in the array > > On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf > wrote: > >> say u choose the last value as pivot >> >> 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 >> >> 4 is your pivot >> try out >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan wrote: >> >>> @rohit : can you give me any counter examples? >>> >>> PS: one value is occuring >=501 times. >>> >>> On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf >> > wrote: >>> >>>> It cannot just be partitioned in such a manner that the middle element >>>> is >>>> *always *the mode ! >>>> >>>> -- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> >>>> >>>> On Thu, Apr 15, 2010 at 11:23 AM, Gauri wrote: >>>> >>>>> Can you illustrate it with an example ? >>>>> How are you deciding the pivot for partitioning the array ? >>>>> How the middle element can be the mode of the array ? >>>>> >>>>> Regards >>>>> Gauri >>>>> >>>>> >>>>> On Apr 14, 5:39 pm, vivek bijlwan wrote: >>>>> > complexity : On) >>>>> > extra - memory required : no >>>>> > >>>>> > have the first iteration of quick sort. return the middle element. >>>>> > >>>>> > >>>>> > >>>>> > On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: >>>>> > > Say If I have an array of 1,000 32-bit integers .And one of the >>>>> value >>>>> > > is occuring 501 number of times or more in the array. Can someone >>>>> help >>>>> > > me devise an efficient algorithm for the same ? >>>>> > >>>>> > > Thanks & Regards >>>>> > > Gauri >>>>> > >>>>> > > -- >>>>> > > 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. >>>>> >>>>> >>>> -- >>>> 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 subs
Re: [algogeeks] Re: Finding the mode in a set of integers
say u choose the last value as pivot 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 4 is your pivot try out -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan wrote: > @rohit : can you give me any counter examples? > > PS: one value is occuring >=501 times. > > On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf > wrote: > >> It cannot just be partitioned in such a manner that the middle element is >> *always *the mode ! >> >> ------ >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> On Thu, Apr 15, 2010 at 11:23 AM, Gauri wrote: >> >>> Can you illustrate it with an example ? >>> How are you deciding the pivot for partitioning the array ? >>> How the middle element can be the mode of the array ? >>> >>> Regards >>> Gauri >>> >>> >>> On Apr 14, 5:39 pm, vivek bijlwan wrote: >>> > complexity : On) >>> > extra - memory required : no >>> > >>> > have the first iteration of quick sort. return the middle element. >>> > >>> > >>> > >>> > On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: >>> > > Say If I have an array of 1,000 32-bit integers .And one of the value >>> > > is occuring 501 number of times or more in the array. Can someone >>> help >>> > > me devise an efficient algorithm for the same ? >>> > >>> > > Thanks & Regards >>> > > Gauri >>> > >>> > > -- >>> > > 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. >>> >>> >> -- >> 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. > -- 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: Finding the mode in a set of integers
It cannot just be partitioned in such a manner that the middle element is *always *the mode ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Apr 15, 2010 at 11:23 AM, Gauri wrote: > Can you illustrate it with an example ? > How are you deciding the pivot for partitioning the array ? > How the middle element can be the mode of the array ? > > Regards > Gauri > > > On Apr 14, 5:39 pm, vivek bijlwan wrote: > > complexity : On) > > extra - memory required : no > > > > have the first iteration of quick sort. return the middle element. > > > > > > > > On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: > > > Say If I have an array of 1,000 32-bit integers .And one of the value > > > is occuring 501 number of times or more in the array. Can someone help > > > me devise an efficient algorithm for the same ? > > > > > Thanks & Regards > > > Gauri > > > > > -- > > > 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. > > -- 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] Finding the mode in a set of integers
*FINAL SOLUTION* :
I gave a second thought :
A large amount of space(but finite constant and bounded and within practical
limits) will eventually be required for my hashing based solution to be
worst case O(n).
So this problem has an linear time solution..
BUT can we do better in terms of space maintaining the time complexity?
Well, I claim that we cannot ! :(
Can anyone disprove/prove that we can do better ??
I don't think the 2 solutions above work
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010 at 10:13 AM, Rohit Saraf
wrote:
> the implementation of the hashmap in prev soln(to achieve constant time) is
> non-trivial and is based on some exercise of Cormen.
>
> better and simple:
>
> Think of these points as nodes of the graph
> use the UnionFind(quickunion) data structure... and everytime a union is
> done add 1 to the component united.
> find the one with count>500
>
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Thu, Apr 15, 2010 at 9:16 AM, Rohit Saraf
> wrote:
>
>> I agree But that worst case will never come here. There are
>> between 2 and 500 keys. And all keys are different So how would
>> the worst case come??
>>
>> On 4/14/10, gaurav kishan wrote:
>> > This will be done in one pass i.e O(n).
>> > On Wed, Apr 14, 2010 at 10:17 PM, gaurav kishan
>> > wrote:
>> >
>> >> Can everyone check this out and let me the issues ?
>> >>
>> >> int[] i=new
>> >> int[]{11,2,3,11,4,11,76,11,11,65,11,44,78,11,13,11,79,11,11,11,56};
>> >> int count=1,element=i[0];
>> >> for(int j=1;j> >> {
>> >>if(element==i[j])
>> >> count++;
>> >>else
>> >>{
>> >> count--;
>> >> if(count==0)
>> >> {
>> >>element=i[j];
>> >> count=1;
>> >> }
>> >> }
>> >>
>> >> }
>> >> System.out.println("Mode is "+element);
>> >> }
>> >>
>> >> Regards,
>> >> Gaurav Kishan
>> >>
>> >> On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar
>> >> wrote:
>> >>
>> >>> ya over here its >501 rite?
>> >>>
>> >>>
>> >>> On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain
>> wrote:
>> >>>
>> >>>> If m thinking right,
>> >>>> That works if mode occurs >=n/2 times in the array
>> >>>>
>> >>>> Best,
>> >>>> Prakhar Jain
>> >>>> http://web.iiit.ac.in/~prakharjain/
>> >>>>
>> >>>>
>> >>>> On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar <
>> aryansmit3...@gmail.com
>> >>>> > wrote:
>> >>>>
>> >>>>> can we make use of majority VOTE ALGORITHM?
>> >>>>>
>> >>>>>
>> >>>>> On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote:
>> >>>>>
>> >>>>>> Say If I have an array of 1,000 32-bit integers .And one of the
>> value
>> >>>>>> is occuring 501 number of times or more in the array. Can someone
>> help
>> >>>>>> me devise an efficient algorithm for the same ?
>> >>>>>>
>> >>>>>> Thanks & Regards
>> >>>>>> Gauri
>> >>>>>>
>> >>>>>> --
>> >>>>>> 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 th
Re: [algogeeks] Finding the mode in a set of integers
the implementation of the hashmap in prev soln(to achieve constant time) is
non-trivial and is based on some exercise of Cormen.
better and simple:
Think of these points as nodes of the graph
use the UnionFind(quickunion) data structure... and everytime a union is
done add 1 to the component united.
find the one with count>500
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010 at 9:16 AM, Rohit Saraf wrote:
> I agree But that worst case will never come here. There are
> between 2 and 500 keys. And all keys are different So how would
> the worst case come??
>
> On 4/14/10, gaurav kishan wrote:
> > This will be done in one pass i.e O(n).
> > On Wed, Apr 14, 2010 at 10:17 PM, gaurav kishan
> > wrote:
> >
> >> Can everyone check this out and let me the issues ?
> >>
> >> int[] i=new
> >> int[]{11,2,3,11,4,11,76,11,11,65,11,44,78,11,13,11,79,11,11,11,56};
> >> int count=1,element=i[0];
> >> for(int j=1;j >> {
> >>if(element==i[j])
> >> count++;
> >>else
> >>{
> >> count--;
> >> if(count==0)
> >> {
> >>element=i[j];
> >> count=1;
> >> }
> >> }
> >>
> >> }
> >> System.out.println("Mode is "+element);
> >> }
> >>
> >> Regards,
> >> Gaurav Kishan
> >>
> >> On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar
> >> wrote:
> >>
> >>> ya over here its >501 rite?
> >>>
> >>>
> >>> On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain
> wrote:
> >>>
> >>>> If m thinking right,
> >>>> That works if mode occurs >=n/2 times in the array
> >>>>
> >>>> Best,
> >>>> Prakhar Jain
> >>>> http://web.iiit.ac.in/~prakharjain/
> >>>>
> >>>>
> >>>> On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar <
> aryansmit3...@gmail.com
> >>>> > wrote:
> >>>>
> >>>>> can we make use of majority VOTE ALGORITHM?
> >>>>>
> >>>>>
> >>>>> On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote:
> >>>>>
> >>>>>> Say If I have an array of 1,000 32-bit integers .And one of the
> value
> >>>>>> is occuring 501 number of times or more in the array. Can someone
> help
> >>>>>> me devise an efficient algorithm for the same ?
> >>>>>>
> >>>>>> Thanks & Regards
> >>>>>> Gauri
> >>>>>>
> >>>>>> --
> >>>>>> 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.
> >>>>>
> >>>>
> >>>> --
> >>>> 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.
> >>>
> >>
> >>
> >
> > --
> > 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.
> >
> >
>
> --
> Sent from my mobile device
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
--
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] Finding the mode in a set of integers
I agree But that worst case will never come here. There are
between 2 and 500 keys. And all keys are different So how would
the worst case come??
On 4/14/10, gaurav kishan wrote:
> This will be done in one pass i.e O(n).
> On Wed, Apr 14, 2010 at 10:17 PM, gaurav kishan
> wrote:
>
>> Can everyone check this out and let me the issues ?
>>
>> int[] i=new
>> int[]{11,2,3,11,4,11,76,11,11,65,11,44,78,11,13,11,79,11,11,11,56};
>> int count=1,element=i[0];
>> for(int j=1;j> {
>>if(element==i[j])
>> count++;
>>else
>>{
>> count--;
>> if(count==0)
>> {
>>element=i[j];
>> count=1;
>> }
>> }
>>
>> }
>> System.out.println("Mode is "+element);
>> }
>>
>> Regards,
>> Gaurav Kishan
>>
>> On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar
>> wrote:
>>
>>> ya over here its >501 rite?
>>>
>>>
>>> On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain wrote:
>>>
>>>> If m thinking right,
>>>> That works if mode occurs >=n/2 times in the array
>>>>
>>>> Best,
>>>> Prakhar Jain
>>>> http://web.iiit.ac.in/~prakharjain/
>>>>
>>>>
>>>> On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar >>> > wrote:
>>>>
>>>>> can we make use of majority VOTE ALGORITHM?
>>>>>
>>>>>
>>>>> On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote:
>>>>>
>>>>>> Say If I have an array of 1,000 32-bit integers .And one of the value
>>>>>> is occuring 501 number of times or more in the array. Can someone help
>>>>>> me devise an efficient algorithm for the same ?
>>>>>>
>>>>>> Thanks & Regards
>>>>>> Gauri
>>>>>>
>>>>>> --
>>>>>> 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.
>>>>>
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>
> --
> 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.
>
>
--
Sent from my mobile device
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
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] Finding the mode in a set of integers
@rizwan : Think!!. *my algorithm is worst case O(n)*.. no doubt ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar wrote: > ya over here its >501 rite? > > > On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain wrote: > >> If m thinking right, >> That works if mode occurs >=n/2 times in the array >> >> Best, >> Prakhar Jain >> http://web.iiit.ac.in/~prakharjain/<http://web.iiit.ac.in/%7Eprakharjain/> >> >> >> On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar wrote: >> >>> can we make use of majority VOTE ALGORITHM? >>> >>> >>> On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: >>> >>>> Say If I have an array of 1,000 32-bit integers .And one of the value >>>> is occuring 501 number of times or more in the array. Can someone help >>>> me devise an efficient algorithm for the same ? >>>> >>>> Thanks & Regards >>>> Gauri >>>> >>>> -- >>>> 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. >>> >> >> -- >> 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. > -- 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] Finding the mode in a set of integers
You are being specific to some programming lang. , I guess. Hashmap refers to hashing in general. On 4/14/10, rizwan hudda wrote: > O(n) is indeed the lower bound of any algorithm on this problem :) > > Yes. O(nlogn) is trivial. > > Sort the given array. > And count the number of occurrences of each element. For some element u ll > get it as 501. U have found that element! > > And about the hashmap based solution. Hashmap internally uses a tree based > structure. So, your 'n' insertion operations will indeed take O(n*logn) > time. > > I guess you meant using "Hashing technique". i,e Using a hash function to > add elements to the bucket array. And then check all the buckets with more > than 500 elements [ since there can be collisions ]. And in one of them > there will be 501 same elements. This soln is going to take O(1) expected > time. > > The open question is to look for an algorithm to find the mode in O(n) worst > case time complexity. > > > On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf > wrote: > >> O(n log n) will be trivial. >> >> O(n) is required at any cost. (Consider the case with 501 "1"s and 499 >> "0"'s) >> >> Ok, so u can make a hashmap with your integer as keys and frequency as the >> value. >>No of keys will be between 2 and 500. (=> Traversing through takes >> O(n) ) >> You will have to traverse the array exactly once => O(n) >> => O(n) solution. >> >> And it cannot be made better ! >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> >> On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: >> >>> Say If I have an array of 1,000 32-bit integers .And one of the value >>> is occuring 501 number of times or more in the array. Can someone help >>> me devise an efficient algorithm for the same ? >>> >>> Thanks & Regards >>> Gauri >>> >>> -- >>> 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. >> > > > > -- > Thanks and regards > Rizwan A Hudda > http://sites.google.com/site/rizwanhudda > > -- > 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. > > -- Sent from my mobile device -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: First k smallest elements
exactly ! But the point is Though i did it in o(n), still the constant will be too high to use.(practically the bst solution will work better for n<10^20 So can we do better?? On 4/14/10, Dave wrote: > Sure, we can build a heap. But what's the point. Already, an O(n) > solution has been identified, using the median of medians algorithm. A > heap would be O(n ln k). > > Dave > > On Apr 14, 4:25 am, Ashish Mishra wrote: >> can't we build a min-heap (kinda opposite of max-heap) ?? >> >> On Wed, Apr 14, 2010 at 8:42 AM, Rohit Saraf >> wrote: >> >> >> >> > Not linear in worst case >> >> > On 4/13/10, souri datta wrote: >> > > what about the algorithm which mimics the Quick Sort and deals with >> > > only >> > one >> > > partition( as in Coremen) ? >> >> > > On Tue, Apr 13, 2010 at 9:11 AM, Rohit Saraf < >> > rohit.kumar.sa...@gmail.com> >> > > wrote: >> >> > >> So tell me something else which works in O(n) >> >> > >> On 4/12/10, souri datta wrote: >> > >> > Why only median of median? >> >> > >> > On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf >> > >> > >> > >> > wrote: >> >> > >> >> Find the kth element using order statistics - O(n) <> As far as >> > >> >> i >> > >> >> know , >> > >> >> u will have to use median of medians selection algorithm for >> > >> >> this... >> > >> >> Rest is fine.. >> >> > >> >> -- >> > >> >> Rohit Saraf >> > >> >> Second Year Undergraduate, >> > >> >> Dept. of Computer Science and Engineering >> > >> >> IIT Bombay >> > >> >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >> On Mon, Apr 12, 2010 at 3:20 PM, souri datta < >> > souri.isthe...@gmail.com> >> > >> >> wrote: >> >> > >> >>> Steps: >> > >> >>> 1. Find the kth element using order statistics - O(n) >> > >> >>> 2. In one pass over the array, get all the elems less than the >> > >> >>> kth >> > >> >>> element. >> >> > >> >>> Let me know if this is not correct. >> >> > >> >>> On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf >> > >> >>> wrote: >> >> > >> >>>> I have already given an O(n) solution. See above ! >> >> > >> >>>> The BST solution is O(nlogn) but is practically more nice. :) >> >> > >> >>>> -- >> > >> >>>> Rohit Saraf >> > >> >>>> Second Year Undergraduate, >> > >> >>>> Dept. of Computer Science and Engineering >> > >> >>>> IIT Bombay >> > >> >>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> > >> >>>> On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal >> > >> >>>> wrote: >> >> > >> >>>>> On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf >> > >> >>>>> wrote: >> >> > >> >>>>>> are yaar... i meant BST... i thought that was obvious ! >> > >> >>>>>> sry if i confused you >> >> > >> >>>>> @rohit It's ok.Actually in this group people come up with very >> > >> >>>>> different and non-common solutions so its risky to take things >> > >> >>>>> 'obviously'. >> > >> >>>>> Rotation algo has a complexity of O(nlogn)[for constructing a >> > >> >>>>> BST] >> > >> >>>>> +O(n) [for rotating n times]=O(nlogn) . >> >> > >> >>>>> Till now best algo we have is using heaps which give rise to >> > >> >>>>> complexity >> > >> >>>>> = O(n+klogn) >> >> > >> >>>>> Please pass on algos having better runtime complexity. >> >> > >> >
Re: [algogeeks] Finding the mode in a set of integers
O(n log n) will be trivial. O(n) is required at any cost. (Consider the case with 501 "1"s and 499 "0"'s) Ok, so u can make a hashmap with your integer as keys and frequency as the value. No of keys will be between 2 and 500. (=> Traversing through takes O(n) ) You will have to traverse the array exactly once => O(n) => O(n) solution. And it cannot be made better ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Apr 14, 2010 at 4:14 PM, Gauri wrote: > Say If I have an array of 1,000 32-bit integers .And one of the value > is occuring 501 number of times or more in the array. Can someone help > me devise an efficient algorithm for the same ? > > Thanks & Regards > Gauri > > -- > 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] First k smallest elements
Find the kth element using order statistics - O(n) <> As far as i know , u will have to use median of medians selection algorithm for this... Rest is fine.. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 3:20 PM, souri datta wrote: > Steps: > 1. Find the kth element using order statistics - O(n) > 2. In one pass over the array, get all the elems less than the kth element. > > Let me know if this is not correct. > > > > On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf > wrote: > >> I have already given an O(n) solution. See above ! >> >> The BST solution is O(nlogn) but is practically more nice. :) >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal < >> nikhil.bhoja...@gmail.com> wrote: >> >>> >>> >>> On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> wrote: >>> >>>> are yaar... i meant BST... i thought that was obvious ! >>>> sry if i confused you >>>> >>> >>> @rohit It's ok.Actually in this group people come up with very different >>> and non-common solutions so its risky to take things 'obviously'. >>> Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) >>> [for rotating n times]=O(nlogn) . >>> >>> Till now best algo we have is using heaps which give rise to complexity = >>> O(n+klogn) >>> >>> Please pass on algos having better runtime complexity. >>> >>>> >>>> >>>> -- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> >>>> >>>> On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal < >>>> nikhil.bhoja...@gmail.com> wrote: >>>> >>>>> Hey rohit.You were referring to Binary tree.Search keyword was >>>>> missing.Because rotation makes no sense in binary tree.Please note binary >>>>> tree and BST are different. >>>>> >>>>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf < >>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>> >>>>>> Read the slides i uploaded. They explain what rotation does in a BST. >>>>>> >>>>>> Also you might like to refer to Red Black Trees in CLRS that >>>>>> chapter explains rotations. >>>>>> >>>>>> -- >>>>>> Rohit Saraf >>>>>> Second Year Undergraduate, >>>>>> Dept. of Computer Science and Engineering >>>>>> IIT Bombay >>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> >>>>>> >>>>>> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf < >>>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>>> >>>>>>> but still the binary tree solution is of more practical use.i will >>>>>>> explain the solution once i reach my comp >>>>>>> >>>>>>> >>>>>>> On 4/11/10, Nikhil Agarwal wrote: >>>>>>> > >>>>>>> > >>>>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>>>>>> rohit.kumar.sa...@gmail.com> >>>>>>> > wrote: >>>>>>> >> >>>>>>> >> Time complexity is O(n log n). But the last solution I gave has >>>>>>> O(n). >>>>>>> >> >>>>>>> >> What did u not understand abt thesolution >>>>>>> > >>>>>>> > >>>>>>> > @Rohit Please explain how that Binary tree solution works. >>>>>>> >> >>>>>>> >> >>>&
Re: [algogeeks] First k smallest elements
I have already given an O(n) solution. See above ! The BST solution is O(nlogn) but is practically more nice. :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal wrote: > > > On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf > wrote: > >> are yaar... i meant BST... i thought that was obvious ! >> sry if i confused you >> > > @rohit It's ok.Actually in this group people come up with very different > and non-common solutions so its risky to take things 'obviously'. > Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) > [for rotating n times]=O(nlogn) . > > Till now best algo we have is using heaps which give rise to complexity = > O(n+klogn) > > Please pass on algos having better runtime complexity. > >> >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal < >> nikhil.bhoja...@gmail.com> wrote: >> >>> Hey rohit.You were referring to Binary tree.Search keyword was >>> missing.Because rotation makes no sense in binary tree.Please note binary >>> tree and BST are different. >>> >>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> wrote: >>> >>>> Read the slides i uploaded. They explain what rotation does in a BST. >>>> >>>> Also you might like to refer to Red Black Trees in CLRS that chapter >>>> explains rotations. >>>> >>>> -- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14 >>>> >>>> >>>> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf < >>>> rohit.kumar.sa...@gmail.com> wrote: >>>> >>>>> but still the binary tree solution is of more practical use.i will >>>>> explain the solution once i reach my comp >>>>> >>>>> >>>>> On 4/11/10, Nikhil Agarwal wrote: >>>>> > >>>>> > >>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>>>> rohit.kumar.sa...@gmail.com> >>>>> > wrote: >>>>> >> >>>>> >> Time complexity is O(n log n). But the last solution I gave has >>>>> O(n). >>>>> >> >>>>> >> What did u not understand abt thesolution >>>>> > >>>>> > >>>>> > @Rohit Please explain how that Binary tree solution works. >>>>> >> >>>>> >> >>>>> >> -- >>>>> >> Rohit Saraf >>>>> >> Second Year Undergraduate, >>>>> >> Dept. of Computer Science and Engineering >>>>> >> IIT Bombay >>>>> >> http://www.cse.iitb.ac.in/~rohitfeb14 >>>>> >> >>>>> >> >>>>> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >>>>> >> wrote: >>>>> >>> >>>>> >>> >>>>> >>> >>>>> >>> On 11 April 2010 10:46, Rohit Saraf >>>>> wrote: >>>>> >>>> >>>>> >>>> Construct a binary tree from the data (maintain the size of >>>>> subtree >>>>> >>>> under each node). >>>>> >>>> Do rotations till the left subtree does not have size k. Rotation >>>>> is a >>>>> >>>> constant time operation. >>>>> >>>> Please prove the correctness of your algorithm with the time >>>>> complexity >>>>> >>>> >>>>> >>>> -- >>>>> >>>> Rohit Saraf >>>>> >>>> Second Year Undergraduate, >>>>> >>>> Dept. of Computer Science and Engineering >>>>> >>&
Re: [algogeeks] First k smallest elements
are yaar... i meant BST... i thought that was obvious ! sry if i confused you -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal wrote: > Hey rohit.You were referring to Binary tree.Search keyword was > missing.Because rotation makes no sense in binary tree.Please note binary > tree and BST are different. > > On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf > wrote: > >> Read the slides i uploaded. They explain what rotation does in a BST. >> >> Also you might like to refer to Red Black Trees in CLRS that chapter >> explains rotations. >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf > > wrote: >> >>> but still the binary tree solution is of more practical use.i will >>> explain the solution once i reach my comp >>> >>> >>> On 4/11/10, Nikhil Agarwal wrote: >>> > >>> > >>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> >>> > wrote: >>> >> >>> >> Time complexity is O(n log n). But the last solution I gave has O(n). >>> >> >>> >> What did u not understand abt thesolution >>> > >>> > >>> > @Rohit Please explain how that Binary tree solution works. >>> >> >>> >> >>> >> -- >>> >> Rohit Saraf >>> >> Second Year Undergraduate, >>> >> Dept. of Computer Science and Engineering >>> >> IIT Bombay >>> >> http://www.cse.iitb.ac.in/~rohitfeb14 >>> >> >>> >> >>> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >>> >> wrote: >>> >>> >>> >>> >>> >>> >>> >>> On 11 April 2010 10:46, Rohit Saraf >>> wrote: >>> >>>> >>> >>>> Construct a binary tree from the data (maintain the size of subtree >>> >>>> under each node). >>> >>>> Do rotations till the left subtree does not have size k. Rotation is >>> a >>> >>>> constant time operation. >>> >>>> Please prove the correctness of your algorithm with the time >>> complexity >>> >>>> >>> >>>> -- >>> >>>> Rohit Saraf >>> >>>> Second Year Undergraduate, >>> >>>> Dept. of Computer Science and Engineering >>> >>>> IIT Bombay >>> >>>> http://www.cse.iitb.ac.in/~rohitfeb14 >>> >>>> >>> >>>> >>> >>>> >>> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond < >>> patidarc...@gmail.com> >>> >>>> wrote: >>> >>>>> >>> >>>>> nice solution appreciate it. but your algorithm is wasting time in >>> >>>>> finding all the element... >>> >>>>> instead of that just find boundary line kth element which can help >>> as >>> >>>>> in finding element greater that kth and element small than kth and >>> that >>> >>>>> soluton can be done in O(N) >>> >>>>> >>> >>>>> >>> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >>> >>>>> wrote: >>> >>>>>> >>> >>>>>> >>> >>>>>> 1) Construct max heap by taking first k elements in an array >>> >>>>>> 2) if k+1 element less than root of max heap >>> >>>>>>a) Delete root of max heap >>> >>>>>>b) Insert k+1 element in max heap and apply heapify method >>> >>>>>> 3) else skip the element >>> >>>>>> 4) apply above procedure for all n elements in an array >>> >>>>>> >>> >>>>>> At last you w
Re: [algogeeks] First k smallest elements
but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal wrote: > > > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf > wrote: >> >> Time complexity is O(n log n). But the last solution I gave has O(n). >> >> What did u not understand abt thesolution > > > @Rohit Please explain how that Binary tree solution works. >> >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >> wrote: >>> >>> >>> >>> On 11 April 2010 10:46, Rohit Saraf wrote: >>>> >>>> Construct a binary tree from the data (maintain the size of subtree >>>> under each node). >>>> Do rotations till the left subtree does not have size k. Rotation is a >>>> constant time operation. >>>> Please prove the correctness of your algorithm with the time complexity >>>> >>>> -- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14 >>>> >>>> >>>> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond >>>> wrote: >>>>> >>>>> nice solution appreciate it. but your algorithm is wasting time in >>>>> finding all the element... >>>>> instead of that just find boundary line kth element which can help as >>>>> in finding element greater that kth and element small than kth and that >>>>> soluton can be done in O(N) >>>>> >>>>> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >>>>> wrote: >>>>>> >>>>>> >>>>>> 1) Construct max heap by taking first k elements in an array >>>>>> 2) if k+1 element less than root of max heap >>>>>> a) Delete root of max heap >>>>>> b) Insert k+1 element in max heap and apply heapify method >>>>>> 3) else skip the element >>>>>> 4) apply above procedure for all n elements in an array >>>>>> >>>>>> At last you will get k smallest elements and root is kth smallest >>>>>> element in the array >>>>>> >>>>>> this is O(nlogk) >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> CHERUVU JAANU REDDY >>>>>> M.Tech in CSIS >>>>>> >>>>>> >>>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy >>>>>> wrote: >>>>>>> >>>>>>> Can any one tell how to do this when there are 'm' queries like >>>>>>> "query i j k" find the kth largest element in between indices i->j in >>>>>>> an array. >>>>>>> When m is large even an O(n) algorithm would be slow. >>>>>>> I thinking that each query could be answered in O(sqrt(n)) time >>>>>>> So any suggestions ? >>>>>>> >>>>>>> Thanks >>>>>>> >>>>>>> >>>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond >>>>>>> wrote: >>>>>>>> >>>>>>>> there are better solution of O(n) are posted in the thread...[?]. >>>>>>>> using order statices >>>>>>>> >>>>>>>> >>>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur >>>>>>>> wrote: >>>>>>>>> >>>>>>>>> Create a temp array temp[0..k-1] of size k. >>>>>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep updating >>>>>>>>> the smallest element of temp[] >>>>>>>>> 3) Return the smallest of temp[] >>>>>>>>> Time Complexity: O((n-k)*k). >>>>>>>>> >>>>>>>>> >>>>>>>>> try it
Re: [algogeeks] First k smallest elements
once u get kth element , u can find first k by a linear travel through the array On 4/11/10, Priyanka Chatterjee wrote: > > > On 11 April 2010 11:06, Rohit Saraf wrote: >> >> I realised now that it can be done easily as : >> we can find the kth largest element in O(n) using Linear general >> selection algorithm - "Median of Medians algorithm" >> >> Well , can we do better than O(n log n ) in creating a BST from an array >> of size n ? > > > Creating a min heap and extracting the k smallest elements can be > implemented in O(n+klogn). So, I think no point creating a BST because it > takes O(nlog n) itself and then searching for k smallest no.s from it would > be another overhead. >> >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> On Sun, Apr 11, 2010 at 10:46 AM, Rohit Saraf >> wrote: >>> >>> Construct a binary tree from the data (maintain the size of subtree under >>> each node). >>> Do rotations till the left subtree does not have size k. Rotation is a >>> constant time operation. >>> >>> -- >>> Rohit Saraf >>> Second Year Undergraduate, >>> Dept. of Computer Science and Engineering >>> IIT Bombay >>> http://www.cse.iitb.ac.in/~rohitfeb14 >>> >>> >>> >>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond >>> wrote: >>>> >>>> nice solution appreciate it. but your algorithm is wasting time in >>>> finding all the element... >>>> instead of that just find boundary line kth element which can help as in >>>> finding element greater that kth and element small than kth and that >>>> soluton can be done in O(N) >>>> >>>> >>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >>>> wrote: >>>>> >>>>> >>>>> 1) Construct max heap by taking first k elements in an array >>>>> 2) if k+1 element less than root of max heap >>>>> a) Delete root of max heap >>>>> b) Insert k+1 element in max heap and apply heapify method >>>>> 3) else skip the element >>>>> 4) apply above procedure for all n elements in an array >>>>> >>>>> At last you will get k smallest elements and root is kth smallest >>>>> element in the array >>>>> >>>>> this is O(nlogk) >>>>> >>>>> >>>>> >>>>> >>>>> CHERUVU JAANU REDDY >>>>> M.Tech in CSIS >>>>> >>>>> >>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy >>>>> wrote: >>>>>> >>>>>> Can any one tell how to do this when there are 'm' queries like "query >>>>>> i j k" find the kth largest element in between indices i->j in an >>>>>> array. >>>>>> When m is large even an O(n) algorithm would be slow. >>>>>> I thinking that each query could be answered in O(sqrt(n)) time >>>>>> So any suggestions ? >>>>>> >>>>>> Thanks >>>>>> >>>>>> >>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond >>>>>> wrote: >>>>>>> >>>>>>> there are better solution of O(n) are posted in the thread...[?]. >>>>>>> using order statices >>>>>>> >>>>>>> >>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur >>>>>>> wrote: >>>>>>>> >>>>>>>> Create a temp array temp[0..k-1] of size k. >>>>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep updating >>>>>>>> the smallest element of temp[] >>>>>>>> 3) Return the smallest of temp[] >>>>>>>> Time Complexity: O((n-k)*k). >>>>>>>> >>>>>>>> >>>>>>>> try it ..for this problem[?] >>>>>>>> >>>>>>>> -- >>>>>>>> You received this message because you
Re: [algogeeks] First k smallest elements
Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee wrote: > > > On 11 April 2010 10:46, Rohit Saraf wrote: > >> Construct a binary tree from the data (maintain the size of subtree under >> each node). >> Do rotations till the left subtree does not have size k. Rotation is a >> constant time operation. >> Please prove the correctness of your algorithm with the time complexity >> >> -- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> >> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond wrote: >> >>> nice solution appreciate it. but your algorithm is wasting time in >>> finding all the element... >>> instead of that just find boundary line kth element which can help as in >>> finding element greater that kth and element small than kth and that soluton >>> can be done in O(N) >>> >>> >>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY < >>> jaanu.cher...@gmail.com> wrote: >>> >>>> >>>> 1) Construct max heap by taking first k elements in an array >>>> 2) if k+1 element less than root of max heap >>>>a) Delete root of max heap >>>>b) Insert k+1 element in max heap and apply heapify method >>>> 3) else skip the element >>>> 4) apply above procedure for all n elements in an array >>>> >>>> At last you will get k smallest elements and root is kth smallest >>>> element in the array >>>> >>>> this is O(nlogk) >>>> >>>> >>>> >>>> >>>> CHERUVU JAANU REDDY >>>> M.Tech in CSIS >>>> >>>> >>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy < >>>> abhijith200...@gmail.com> wrote: >>>> >>>>> Can any one tell how to do this when there are 'm' queries like "query >>>>> i j k" find the kth largest element in between indices i->j in an array. >>>>> When m is large even an O(n) algorithm would be slow. >>>>> I thinking that each query could be answered in O(sqrt(n)) time >>>>> So any suggestions ? >>>>> >>>>> Thanks >>>>> >>>>> >>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond >>>>> wrote: >>>>> >>>>>> there are better solution of O(n) are posted in the thread...[?]. >>>>>> using order statices >>>>>> >>>>>> >>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur < >>>>>> mukeshraj8...@gmail.com> wrote: >>>>>> >>>>>>> Create a temp array temp[0..k-1] of size k. >>>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep updating >>>>>>> the smallest element of temp[] >>>>>>> 3) Return the smallest of temp[] >>>>>>> Time Complexity: O((n-k)*k). >>>>>>> >>>>>>> >>>>>>> try it ..for this problem[?] >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> BL/\CK_D!AMOND >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>&g
Re: [algogeeks] First k smallest elements
I realised now that it can be done easily as : we can find the kth largest element in O(n) using Linear general selection algorithm - "Median of Medians algorithm" Well , can we do better than O(n log n ) in creating a BST from an array of size n ? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Apr 11, 2010 at 10:46 AM, Rohit Saraf wrote: > Construct a binary tree from the data (maintain the size of subtree under > each node). > Do rotations till the left subtree does not have size k. Rotation is a > constant time operation. > > ------ > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > > > > On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond wrote: > >> nice solution appreciate it. but your algorithm is wasting time in finding >> all the element... >> instead of that just find boundary line kth element which can help as in >> finding element greater that kth and element small than kth and that soluton >> can be done in O(N) >> >> >> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY < >> jaanu.cher...@gmail.com> wrote: >> >>> >>> 1) Construct max heap by taking first k elements in an array >>> 2) if k+1 element less than root of max heap >>>a) Delete root of max heap >>>b) Insert k+1 element in max heap and apply heapify method >>> 3) else skip the element >>> 4) apply above procedure for all n elements in an array >>> >>> At last you will get k smallest elements and root is kth smallest element >>> in the array >>> >>> this is O(nlogk) >>> >>> >>> >>> >>> CHERUVU JAANU REDDY >>> M.Tech in CSIS >>> >>> >>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy < >>> abhijith200...@gmail.com> wrote: >>> >>>> Can any one tell how to do this when there are 'm' queries like "query i >>>> j k" find the kth largest element in between indices i->j in an array. >>>> When m is large even an O(n) algorithm would be slow. >>>> I thinking that each query could be answered in O(sqrt(n)) time >>>> So any suggestions ? >>>> >>>> Thanks >>>> >>>> >>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond wrote: >>>> >>>>> there are better solution of O(n) are posted in the thread...[?]. >>>>> using order statices >>>>> >>>>> >>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur < >>>>> mukeshraj8...@gmail.com> wrote: >>>>> >>>>>> Create a temp array temp[0..k-1] of size k. >>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep updating the >>>>>> smallest element of temp[] >>>>>> 3) Return the smallest of temp[] >>>>>> Time Complexity: O((n-k)*k). >>>>>> >>>>>> >>>>>> try it ..for this problem[?] >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> BL/\CK_D!AMOND >>>>> >>>>> -- >>>>> 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: Implement a queue using a stack
hmm... that can always be done ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Mar 24, 2010 at 6:24 PM, Dave wrote: > Please post your results. I'd like to study your algorithm. > > On Mar 23, 11:15 pm, chitta koushik > wrote: > > yeah i understand that . still wanted to attempt writing a recursive > > reverse() stack operation. > > > > On Wed, Mar 24, 2010 at 9:21 AM, Rohit Saraf < > rohit.kumar.sa...@gmail.com>wrote: > > > > > > > > > Even when you are writing a recursive function.. you are not using one > > > stack. > > > One stack is yours. Other used for recursion. > > > > > Making queue from a single stack <=> Making turing machine from CFG. > > > > > -Rohit > > > > > On Wed, Mar 24, 2010 at 9:18 AM, chitta koushik < > > > koushik.infin...@gmail.com> wrote: > > > > >> Can we implement it using a single stack by writing a recursive > reverse > > >> stack operation ? > > > > >> On Tue, Mar 23, 2010 at 10:18 AM, Sundeep Singh < > singh.sund...@gmail.com>wrote: > > > > >>> Thanks Dave, I didn't think about this... definitely better! > > > > >>> Sundeep. > > > > >>> On Mon, Mar 22, 2010 at 9:08 PM, Dave > wrote: > > > > >>>> Better still. > > >>>> To enqueue: push onto stack A. > > >>>> For dequeuing: If stack B is empty, pop all items from stack A and > > >>>> push onto stack B. Then pop stack B. > > >>>> There is no need to push remaining items back to stack A. > > > > >>>> As every item passes through the queue, it is pushed onto stack A, > > >>>> then popped from stack A and pushed onto stack B, and finally popped > > >>>> from stack B. The time is roughly twice the time required for a > direct > > >>>> implementation of a queue. > > > > >>>> There is room for a little optimization if both stacks are empty > when > > >>>> enquing, as you can push the item directly onto stack B. > Furthermore, > > >>>> when popping from stack A and pushing onto stack B, you don't need > to > > >>>> push the last item popped, as it is the return value. > > > > >>>> Dave > > > > >>>> On Mar 22, 9:29 am, Sundeep Singh wrote: > > >>>> > Hey Brian, > > > > >>>> > Better still, for inserting in queue, just keep pushing onto the > stack > > >>>> A. > > >>>> > You need stack B only for dequeuing: for dequeuing, push all items > > >>>> into > > >>>> > stack B, pop as many as you want from stack B and then push back > all > > >>>> > remaining items in stack A. > > > > >>>> > Regards, > > >>>> > Sundeep. > > > > >>>> > On Mon, Mar 22, 2010 at 6:56 PM, Brian > wrote: > > >>>> > > > How is it possible to implement a queue using a stack only? > > > > >>>> > > Interesting, but tricky... You need two stacks as Prakhar > stated... > > >>>> > > In general, if you have Stack A and Stack B, you should keep all > the > > >>>> items > > >>>> > > in stack A and then use stack B for processing. > > > > >>>> > > For example to insert an item: > > >>>> > > 1. Pop all the items from A and then push them into B (this > should > > >>>> push > > >>>> > > the items into Stack B in reverse order) > > >>>> > > 2. Insert the new item into A > > >>>> > > 3. Pop all the items in B and push them back into A (again this > will > > >>>> push > > >>>> > > them back into Stack B in reverse order) > > > > >>>> > > Running time should be O(1)+O(2n), which is O(n) for larger > values > > >>>> of n - > > >>>> > > which is not good... > > > > >>>> > > To retrieve an item, pop the first item in stack A > > > > >>>> > > Hope this helps - > > >>>> > > Regards > > >>>> > > B > &
Re: [algogeeks] First k smallest elements
Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond wrote: > nice solution appreciate it. but your algorithm is wasting time in finding > all the element... > instead of that just find boundary line kth element which can help as in > finding element greater that kth and element small than kth and that soluton > can be done in O(N) > > > On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY < > jaanu.cher...@gmail.com> wrote: > >> >> 1) Construct max heap by taking first k elements in an array >> 2) if k+1 element less than root of max heap >>a) Delete root of max heap >>b) Insert k+1 element in max heap and apply heapify method >> 3) else skip the element >> 4) apply above procedure for all n elements in an array >> >> At last you will get k smallest elements and root is kth smallest element >> in the array >> >> this is O(nlogk) >> >> >> >> >> CHERUVU JAANU REDDY >> M.Tech in CSIS >> >> >> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy > > wrote: >> >>> Can any one tell how to do this when there are 'm' queries like "query i >>> j k" find the kth largest element in between indices i->j in an array. >>> When m is large even an O(n) algorithm would be slow. >>> I thinking that each query could be answered in O(sqrt(n)) time >>> So any suggestions ? >>> >>> Thanks >>> >>> >>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond wrote: >>> >>>> there are better solution of O(n) are posted in the thread...[?]. >>>> using order statices >>>> >>>> >>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur < >>>> mukeshraj8...@gmail.com> wrote: >>>> >>>>> Create a temp array temp[0..k-1] of size k. >>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep updating the >>>>> smallest element of temp[] >>>>> 3) Return the smallest of temp[] >>>>> Time Complexity: O((n-k)*k). >>>>> >>>>> >>>>> try it ..for this problem[?] >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> BL/\CK_D!AMOND >>>> >>>> -- >>>> 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. >>> >> >> -- >> 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. >> > > > > -- > BL/\CK_D!AMOND > > -- > 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. <<338.gif>><<361.gif>>
Re: [algogeeks] Finding all prime less than 10^8
why don't you remove all even numbers from consideration and add 2
explicitly. I think that would help.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond wrote:
> i have an problem on SPOJ to find all the prime less than 10^8
> https://www.spoj.pl/problems/TDPRIMES/
>
> i am using sieve of erastosthenes algorithm to find primes
> my code is taking in my machine around 10.9 to 11.2 seconds
> and time limit is 10 second how i can change my code or any diff logic..???
> //-//
> #include
> using namespace std;
> #define ten8 (1)
> bool M[ten8];
> int main()
> {
> int half=1, i,j,x=0;
> for ( i = 0;i < ten8;i++)
> M[i] = false;
> for ( i = 2;i < ten8;i++)
> {
> if (M[i] == false)
> {
> x++;
> if(x%100==1)
> printf("%d\n",i);
> if(i>half)
> continue;
>
> for (int j = i * i;j < ten8;j += i)
> {
> M[j] = true;
> }
> }
> }
> }
>
> --
> 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] efficient backtracking algorithm for the coin changing problem
What do u mean by "y u need backtracking " DP needs backtracking to reconstruct the solution. -Rohit On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra wrote: > y u need backtracking > i think it can be done with DP > > On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» wrote: > >> Need help in designing efficient backtracking algorithm for the coin >> changing problem. where a1, a2, an are the set of distinct coins >> types, where each ai is an integer. and each type is unlimited >> quantity. >> >> the problem to make up the exact amount C using minimum total number >> of coins. use backtracking template with a bounding function.. >> >> help appreciated.. >> >> -- >> 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. >> >> > > > -- > How soon 'not now' becomes 'never'... > > -- > 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] Graph MST problem
a) Consider green 1 red 1 | | green 2 | | *imagine diagonals* with red 500 and red 2. Could not explain better without diagram... hope it's clear b) Make a spanning tree of red. Now modify the weights of green as = original weight - max weight of the red that can be replaced on adding this in the cycle formed. Include the min wt green edge. Proof trivial -Rohit On Sat, Apr 3, 2010 at 11:38 PM, shruti s wrote: > Hi, > > Please help me to solve following problems > > Let > *G *= (*V; E;w*) be a weighted undirected graph whose edges are colored > either > > red or green. That is > *E *= *Er [ Eg *and *Er \ Eg *= *;*, where *Er *are the red edges > > and > *Eg *are the green edges. Assume that all edge weights are distinct (so > that the > > minimum spanning tree is unique). Also assume that there is at least one > green edge. > > Suppose that the minimum spanning tree, > *T*0, consists entirely of red edges. Let *T*1 be > > the minimum-cost tree among the spanning trees that have exactly one green > edge. > > (a) Show, by giving an example, that > *T*1 does not necessarily include the lowset-cost > > green edge. > > (b) Prove that > *T*1 can be obtained from *T*0 by swapping a red edge for a green > > edge. That is, there exists a green edge > (*u; v*) and a red edge (*x; y*) such that *T*1 =* > T > *0 *[ f*(*u; v*)*g ¡ f*(*x; y*)*g*. > > > Thanks > > -- > 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.
