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 <[email protected]>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 <[email protected] > > 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 <[email protected] >> > 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 <[email protected]> wrote: >>> > >>> > >>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>> [email protected]> >>> > 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 >>> >> <[email protected]> wrote: >>> >>> >>> >>> >>> >>> >>> >>> On 11 April 2010 10:46, Rohit Saraf <[email protected]> >>> 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 < >>> [email protected]> >>> >>>> 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 >>> >>>>> <[email protected]> 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 >>> >>>>>> <[email protected]> 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 < >>> [email protected]> >>> >>>>>>> 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 >>> >>>>>>>> <[email protected]> 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 >>> [email protected]. >>> >>>>>>>>> To unsubscribe from this group, send email to >>> >>>>>>>>> [email protected]<algogeeks%[email protected]> >>> . >>> >>>>>>>>> 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 [email protected] >>> . >>> >>>>>>>> To unsubscribe from this group, send email to >>> >>>>>>>> [email protected]<algogeeks%[email protected]> >>> . >>> >>>>>>>> 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 [email protected]. >>> >>>>>>> To unsubscribe from this group, send email to >>> >>>>>>> [email protected]<algogeeks%[email protected]> >>> . >>> >>>>>>> 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 [email protected]. >>> >>>>>> To unsubscribe from this group, send email to >>> >>>>>> [email protected]<algogeeks%[email protected]> >>> . >>> >>>>>> 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 [email protected]. >>> >>>>> To unsubscribe from this group, send email to >>> >>>>> [email protected]<algogeeks%[email protected]> >>> . >>> >>>>> 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 [email protected]. >>> >>>> To unsubscribe from this group, send email to >>> >>>> [email protected]<algogeeks%[email protected]> >>> . >>> >>>> 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 [email protected]. >>> >>> To unsubscribe from this group, send email to >>> >>> [email protected]<algogeeks%[email protected]> >>> . >>> >>> 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 [email protected]. >>> >> To unsubscribe from this group, send email to >>> >> [email protected]<algogeeks%[email protected]> >>> . >>> >> 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 [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]<algogeeks%[email protected]> >>> . >>> > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<338.gif>>
<<361.gif>>
