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 > > > 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 <nikhil.bhoja...@gmail.com> 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 >>>> >> <dona.1...@gmail.com> wrote: >>>> >>> >>>> >>> >>>> >>> >>>> >>> On 11 April 2010 10:46, Rohit Saraf <rohit.kumar.sa...@gmail.com> >>>> 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 >>>> >>>>> <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 < >>>> patidarc...@gmail.com> >>>> >>>>>>> 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> >>>>>>>> For more options, visit this group at >>>> >>>>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>>>>> >>>> >>>>>>> >>>> >>>>>>> -- >>>> >>>>>>> You received this message because you are subscribed to the >>>> Google >>>> >>>>>>> Groups "Algorithm Geeks" group. >>>> >>>>>>> To post to this group, send email to algogeeks@googlegroups.com >>>> . >>>> >>>>>>> To unsubscribe from this group, send email to >>>> >>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> >>>>>>> For more options, visit this group at >>>> >>>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>>>> >>>> >>>>>> >>>> >>>>>> -- >>>> >>>>>> You received this message because you are subscribed to the >>>> Google >>>> >>>>>> Groups "Algorithm Geeks" group. >>>> >>>>>> To post to this group, send email to algoge...@googlegroups.com. >>>> >>>>>> To unsubscribe from this group, send email to >>>> >>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> >>>>> For more options, visit this group at >>>> >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>>> >>>> >>>> >>>> -- >>>> >>>> You received this message because you are subscribed to the Google >>>> >>>> Groups "Algorithm Geeks" group. >>>> >>>> To post to this group, send email to algoge...@googlegroups.com. >>>> >>>> To unsubscribe from this group, send email to >>>> >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> >>>> For more options, visit this group at >>>> >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>>> >>> >>>> >>> >>>> >>> >>>> >>> -- >>>> >>> Thanks & Regards, >>>> >>> Priyanka Chatterjee >>>> >>> Third Year Undergraduate Student, >>>> >>> Computer Science & Engineering, >>>> >>> National Institute Of Technology,Durgapur >>>> >>> India >>>> >>> http://priyanka-nit.blogspot.com/ >>>> >>> >>>> >>> -- >>>> >>> You received this 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<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> >>> For more options, visit this group at >>>> >>> http://groups.google.com/group/algogeeks?hl=en. >>>> >> >>>> >> >>>> >> -- >>>> >> You received this message because you are subscribed to the Google >>>> Groups >>>> >> "Algorithm Geeks" group. >>>> >> To post to this group, send email to algoge...@googlegroups.com. >>>> >> To unsubscribe from this group, send email to >>>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> >> For more options, visit this group at >>>> >> http://groups.google.com/group/algogeeks?hl=en. >>>> > >>>> > >>>> > >>>> > >>>> > -- >>>> > Thanks & Regards >>>> > Nikhil Agarwal >>>> > Junior Undergraduate >>>> > Computer Science & Engineering, >>>> > National Institute Of Technology, Durgapur,India >>>> > http://tech-nikk.blogspot.com >>>> > >>>> > >>>> > -- >>>> > You received this 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards >> Nikhil Agarwal >> Junior Undergraduate >> Computer Science & Engineering, >> National Institute Of Technology, Durgapur,India >> http://tech-nikk.blogspot.com >> >> >> -- >> You received this 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards Nikhil Agarwal Junior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this 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>>
